Haskell / Miranda: Find the type of the function

Question

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!

Answer 1

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]

Answer 2

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 swapping 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