Haskell / Miranda: Find the type of the function
-
04-06-2021 - |
Вопрос
Brief: This is a past exam question from a Miranda exam but the syntax is very similar to Haskell.
Question: What is the type of the following expression and what does it do? (The definitions of the functions length and swap are given below).
(foldr (+) 0) . (foldr ((:) . length . (swap (:) [] )) [])
length [] = 0
length (x:xs) = 1 + length xs
swap f x y = f y x
Note:
Please feel free to reply in haskell syntax - sorry about putting using the stars as polytypes but i didn't want to translate it incorrectly into haskell. Basically, if one variable has type * and the other has * it means they can be any type but they must both be the same type. If one has ** then it means that it can but does not need to have the same type as *. I think it corresponds to a,b,c etc in haskell usuage.
My working so far
From the definition of length you can see that it finds the length of a list of anything so this gives
length :: [*] -> num.
From the definition I think swap takes in a function and two parameters and produces the function with the two parameters swapped over, so this gives
swap :: (* -> ** -> ***) -> ** -> [*] -> ***
foldr takes a binary function (like plus) a starting value and list and folds the list from right to left using that function. This gives
foldr :: (* -> ** -> **) -> ** -> [*] -> **)
I know in function composition it is right associative so for example everything to the right of the first dot (.) needs to produce a list because it will be given as an argument to the first foldr.
The foldr function outputs a single value ( the result of folding up the list) so I know that the return type is going to be some sort of polytype and not a list of polytype.
My problem
I'm unsure where to go from here really. I can see that swap needs to take in another argument, so does this partial application imply that the whole thing is a function? I'm quite confused!
Решение
You've already got the answer, I'll just write down the derivation step by step so it's easy to see all at once:
xxf xs = foldr (+) 0 . foldr ((:) . length . flip (:) []) [] $ xs
= sum $ foldr ((:) . length . (: [])) [] xs
= sum $ foldr (\x -> (:) (length [x])) [] xs
= sum $ foldr (\x r -> length [x]:r) [] xs
= sum $ map (\x -> length [x] ) xs
= sum [length [x] | x <- xs]
= sum [ 1 | x <- xs]
-- = length xs
xxf :: (Num n) => [a] -> n
So that, in Miranda, xxf xs = #xs
. I guess its type is :: [*] -> num
in Miranda syntax.
Haskell's length
is :: [a] -> Int
, but as defined here, it is :: (Num n) => [a] -> n
because it uses Num
's (+)
and two literals, 0
and 1
.
If you're having trouble visualizing foldr
, it is simply
foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...))))))
= a+(b+(c+(d+(e+(...+(z+ 0)...)))))
= sum [a, b, c, d, e, ..., z]
Другие советы
Let's go through this step-by-step.
The length
function obviously has the type that you described; in Haskell it's Num n => [a] -> n
. The equivalent Haskell function is length
(It uses Int
instead of any Num n
).
The swap
function takes a function to invoke and reverses its first two arguments. You didn't get the signature quite right; it's (a -> b -> c) -> b -> a -> c
. The equivalent Haskell function is flip
.
The foldr
function has the type that you described; namely (a -> b -> b) -> b -> [a] -> b
. The equivalent Haskell function is foldr
.
Now, let's see what each sub expression in the main expression means.
The expression swap (:) []
takes the (:)
function and swaps its arguments. The (:)
function has type a -> [a] -> [a]
, so swap
ping it yields [a] -> a -> [a]
; the whole expression thus has type a -> [a]
because the swapped function is applied to []
. What the resulting function does is that it constructs a list of one item given that item.
For simplicity, let's extract that part into a function:
singleton :: a -> [a]
singleton = swap (:) []
Now, the next expression is (:) . length . singleton
. The (:)
function still has type a -> [a] -> [a]
; what the (.)
function does is that it composes functions, so if you have a function foo :: a -> ...
and a function bar :: b -> a
, foo . bar
will have type b -> ...
. The expression (:) . length
thus has type Num n => [a] -> [n] -> [n]
(Remember that length
returns a Num
), and the expression (:) . length . singleton
has type Num => a -> [n] -> [n]
. What the resulting expression does is kind of strange: given any value of type a
and some list, it will ignore the a
and prepend the number 1
to that list.
For simplicity, let's make a function out of that:
constPrependOne :: Num n => a -> [n] -> [n]
constPrependOne = (:) . length . singleton
You should already be familiar with foldr
. It performs a right-fold over a list using a function. In this situation, it calls constPrependOne
on each element, so the expression foldr constPrependOne []
just constructs a list of ones with equal length to the input list. So let's make a function out of that:
listOfOnesWithSameLength :: Num n => [a] -> [n]
listOfOnesWithSameLength = foldr constPrependOne []
If you have a list [2, 4, 7, 2, 5]
, you'll get [1, 1, 1, 1, 1]
when applying listOfOnesWithSameLength
.
Then, the foldr (+) 0
function is another right-fold. It is equivalent to the sum
function in Haskell; it sums the elements of a list.
So, let's make a function:
sum :: Num n => [n] -> n
sum = foldr (+) 0
If you now compose the functions:
func = sum . listOfOnesWithSameLength
... you get the resulting expression. Given some list, it creates a list of equal length consisting of only ones, and then sums the elements of that list. It does in other words behave exactly like length
, only using a much slower algorithm. So, the final function is:
inefficientLength :: Num n => [a] -> n
inefficientLength = sum . listOfOnesWithSameLength