Haskell / Miranda: Find the type of the function

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