How to read this functional code

Question

Having trouble reading (interpreting) this functional Miranda code.

g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])

I know what it does

• Calculate the size of a list by taking the length via #
• Creating a one element list containing the above length of the original input list
• Collapsing the new list using foldr into a single integer with the operation +0 on each element

However I am confused by the brackets and don't see where the input list is fed in. What does the rightmost [] constructor do?

Also why does this code only work via the function g, but if I call it directly it throws an error?

Answer 1

In short, g is a function that returns the length of the list.

Let's break the function into some parts.

|| returns 1 for any input.
||   return_one "hoobar" = 1
return_one :: * -> num
return_one = (#) . (:[]) 

|| ignore first argument, insert 1 to the second argument.
||   insert_one "hoobar" [4,5,6] = [1,4,5,6]
insert_one :: *->[num]->[num]
insert_one = (:) . return_one

|| sum of list.
||   sum_list [7,8,9] = 24
sum_list :: [num] -> num 
sum_list = foldr (+) 0

|| generate list of 1 which as the same length of original list. 
||   change_one ["apple","banana"] = [1,1]
change_one :: [*] -> [num]
change_one = foldr insert_one []

|| return the length of the list.
||   g ["apple","banana"] = 2
g :: [*] -> num
g = sum_list . change_one

I would explain some confusing functions.

return_one

(:[]) is a function that creates single element list, and (#) returns the length. Strictly speaking, (:[]) is (:) which takes [] as first argument.

therefore (:[]) "hoobar" = "hoobar":[] = ["hoobar"], and applying (#) to it returns 1.

change_one

It starts with empty list [] and traverses through the list with inserting 1 to the front.

foldr insert_one [] ["apple","banana"]
= foldr insert_one [1] ["apple"]
= foldr insert_one [1,1] []

Answer 2

I don't know Miranda too well, but based on Haskell (I believe the differences between the two here would be minor, with only the # being a unary operator for list length being the only semi-significant one and with || being the comment syntax): The . is function composition:

(p . q) x = p (q x)
  || also can be written as:
p . q = \x -> p (q x)

Function composition is an associative operation, so p . (q . r) = (p . q) . r = p . q . r.

Using this information, we can expand this with the definition of .:

g      = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])       || Original definition
g list = foldr (+) 0 (foldr ((:) . ((#) . (:[]))) [] list)
g list = foldr (+) 0 (foldr (\x -> (:) (((#) . (:[])) x)) [] list)
g list = foldr (+) 0 (foldr (\x -> (:) ((\y -> (#) ((:[]) y)) x)) [] list)

This can be cleaned up some more:

g list = foldr (+) 0 (foldr (\x -> (:) ((\y -> (#)(y:[])) x)) [] list) || More conventional operator syntax for the innermost `:`
g list = foldr (+) 0 (foldr (\x -> (:) ((#)(x:[]))) [] list)           || Innermost lambda was applied to x. Substitute y for x.
g list = foldr (+) 0 (foldr (\x -> (:) ((#)([x]))) [] list)            || Apply innermost `:`
g list = foldr (+) 0 (foldr (\x -> (:) #[x])) [] list)                 || Remove unnecessary parentheses
g list = foldr (+) 0 (foldr (\x acc -> (:) (#[x]) acc) [] list)        || Explicitly write implicit argument. This particular step is called eta-expansion
g list = foldr (+) 0 (foldr (\x acc -> (:) 1 acc) [] list)             || #[x] is always 1, no matter what x is
g list = foldr (+) 0 (foldr (\x acc -> 1 : acc) [] list)               || More conventional syntax for `:`

Also note that the foldr doesn't apply +0 to every element, as you've stated in the question. foldr op z (a:b:c:[]) becomes op a (op b (op c z))) (a:b:c:[] is another way to write [a,b,c]). I always thought this diagram is helpful to understand that:

Additionally, most likely the reason that you got an error when calling it directly is that p . q x is not the same as (p . q) x.