Haskell / Miranda: find function type

Question

Summary: This is a Miranda exam exam question, but the syntax is very similar to Haskell.

Question: What is the type of the following expression and what does it do? (Definitions from the length and swap functions are given below).

(foldr (+) 0) . (foldr ((:) . length . (swap (:) [] )) []) length [] = 0 length (x:xs) = 1 + length xs swap fxy = fyx 

Note:

Please feel free to answer in the haskell syntax - sorry to use stars as polytypes, but I did not want to translate it incorrectly into haskell. Basically, if one variable has type *, and the other has *, this means that they can be of any type, but both must be of the same type. If you have **, this means that it can, but should not be of the same type as *. I think it matches a, b, c, etc. In haskell usuage.

My work is still

From the definition of length, you can see that it finds the length of the list, so this gives

 length :: [*] -> num. 

From the definition, I think that swap takes a function and two parameters and produces a function with two changed parameters, so this gives

 swap :: (* -> ** -> ***) -> ** -> [*] -> *** 

foldr takes a binary function (e.g., plus) the initial value and the list and flushes the list from right to left using this function. This gives

 foldr :: (* -> ** -> **) -> ** -> [*] -> **) 

I know that in the composition of the function it is the correct associative, so, for example, everything that is to the right of the first dot (.) Should create 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 the list), so I know that the return type will be a kind of politician, not a political type.

My problem

I'm not sure where to go from here. I see that the exchange must accept another argument, just as this partial application implies that all this is a function? I am completely embarrassed!

Answer 1

You already have the answer, I’ll just record the derivation step by step so that it is easy to see everything at once:

 xxf xs = foldr (+) 0 . foldr ((:) . length . flip (:) []) [] $ xs == sum $ foldr ((:) . length . (: [])) [] xs == sum $ foldr (\x -> (:) (length [x])) [] xs == sum $ foldr (\xr -> 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 in Miranda, xxf xs = #xs . I think its type :: [*] -> num in the Miranda syntax.

Haskell length is :: [a] -> Int , but as defined here, it is :: (Num n) => [a] -> n because it uses Num (+) and two literals 0 and 1 .

If you are having trouble visualizing foldr , it's just

 foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...)))))) == a+(b+(c+(d+(e+(...+(z+ 0)...))))) == sum [a,b,c,d,e,...,z] 

Answer 2

Skip this step by step.

The length function obviously has the type you described; in Haskell it Num n => [a] -> n . Equivalent Haskell length function (it uses Int instead of any Num n ).

The swap function takes a function to call and change its first two arguments. You did not receive the signature quite correctly; this is (a -> b -> c) -> b -> a -> c . Equivalent Haskell flip function.

The foldr function is of the type that you described; namely (a -> b -> b) -> b -> [a] -> b . Equivalent Haskell foldr function.

Now let's see what each auxiliary expression in the main expression means.

The expression swap (:) [] takes a function (:) and swaps its arguments. The function (:) is of type a -> [a] -> [a] , so swap ping gives [a] -> a -> [a] ; Thus, the whole expression is of type a -> [a] , because the swapped function is applied to [] . What the resulting function does is that it builds a list of one item specified by that item.

For simplicity, return this part to the function:

 singleton :: a -> [a] singleton = swap (:) [] 

Now the following expression (:) . length . singleton (:) . length . singleton (:) . length . singleton . Function (:) is still of type a -> [a] -> [a] ; what the function (.) does is that it makes up the functions, so if you have a function foo :: a -> ... and a function bar :: b -> a , foo . bar foo . bar will be of type b -> ... Expression (:) . length (:) . length is of type Num n => [a] -> [n] -> [n] (remember that length returns a Num ), and the expression (:) . length . singleton (:) . length . singleton (:) . length . singleton is of type Num => a -> [n] -> [n] . That the resulting expression does this is strange: given any value of type a and some list, it ignores a and adds the number 1 to this list.

For simplicity, we will make a function out of this:

 constPrependOne :: Num n => a -> [n] -> [n] constPrependOne = (:) . length . singleton 

You should already be familiar with foldr . He performs the right shift above the list using the function. In this situation, it calls constPrependOne for each element, so the expression foldr constPrependOne [] simply creates a list of them with an equal length in the input list. So make a function out of this:

 listOfOnesWithSameLength :: Num n => [a] -> [n] listOfOnesWithSameLength = foldr constPrependOne [] 

If you have a list of [2, 4, 7, 2, 5] , you will get [1, 1, 1, 1, 1] when applying listOfOnesWithSameLength .

Then the function foldr (+) 0 is the other right button. This is equivalent to the sum function in Haskell; he summarizes the elements of the list.

So, create a function:

 sum :: Num n => [n] -> n sum = foldr (+) 0 

If you are now composing functions:

 func = sum . listOfOnesWithSameLength 

... you will get the resulting expression. Given a list, it creates a list of equal length, consisting of only one, and then summarizes the elements of this list. In other words, it behaves exactly the same as length , using only a slower algorithm. So the final function:

 inefficientLength :: Num n => [a] -> n inefficientLength = sum . listOfOnesWithSameLength