如何解读这段Miranda函数式代码？两处疑问寻求解答

Let's break down this code line by line to unpack its structure, input flow, and behavior:

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

First, recall how function composition works #

In Miranda (and most functional languages), the . operator composes two functions: f . g means "apply g first, then pass its result to f". Formally, (f . g) x = f (g x). So g here is a composite function—its input gets passed to the right-hand foldr first, then the output of that goes to the left-hand foldr.

Step 1: Unpack the right-hand foldr #

Let's start with the inner nested functions, working from right to left:

• (:[]): This is a function that takes any value and wraps it in a single-element list. For any x, x :[] = [x].
• (#) . (:[]): Composing the length function # with (:[]) gives us \x -> # (x :[]). Since a single-element list always has length 1, this simplifies to a constant function: it returns 1 for any input x.
• (:) . ((#) . (:[])): Now we compose the list constructor (:) with the above constant function. This becomes \x -> (:) 1—a function that takes an accumulator list and prepends 1 to it (i.e., \acc -> 1 : acc).

So the right-hand foldr simplifies to:

foldr (\x acc -> 1 : acc) []

What does this do? For an input list like [a, b, c], it traverses each element, ignores the element itself, and prepends 1 to the accumulator. Starting with the initial value [], we get:
1 : (1 : (1 : [])) = [1, 1, 1]
In short: this foldr converts the input list into a list of 1s with the same length as the original list.

Step 2: Unpack the left-hand foldr #

The left-hand side is foldr (+) 0—a standard sum function. It takes a list of numbers and folds them up by adding, starting with 0. For our example [1,1,1], this gives 1+1+1+0 = 3—which is exactly the length of the original input list.

Answering your specific questions #

1. Where does the input list get passed? #

Since g is f . h (where f is the sum foldr, h is the 1-list foldr), calling g myList is equivalent to f (h myList). The input myList first goes to h (the right-hand foldr), which turns it into a list of 1s. That result is then passed to f (the left-hand foldr) to compute the sum (aka the original list's length).

2. What's the purpose of the rightmost []? #

That's the initial accumulator value for the right-hand foldr. When foldr processes an empty input list, it returns this initial value directly. For example, if you pass [] to g, the right-hand foldr returns [], then the left-hand foldr sums [] to get 0—matching the behavior of the standard # function for empty lists.

3. Why does direct invocation fail, but calling g works? #

The issue is operator precedence. In Miranda, function application has higher precedence than the composition operator ..

If you try to run:

(foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) []) [1,2,3]

The parser will first evaluate (foldr ((:) . ((#) . (:[]))) []) [1,2,3] (since function application is higher priority), resulting in [1,1,1]. Then it tries to compute (foldr (+)0) . [1,1,1]—but . requires two functions as arguments, not a function and a list. This causes a type error.

When you bind the composite function to g, g [1,2,3] is parsed as (g) [1,2,3]—the entire composite function is applied to the input list, which is valid. To call it directly without binding to g, you need to wrap the entire composite function in parentheses:

((foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) [])) [1,2,3]

This tells the parser to treat the composition as a single function before applying it to the input list.

内容的提问来源于stack exchange，提问作者clicky