Interesting observations Daniel. You're right; you're implementation is more compact for sure.

An even neater feature of the list comprehension

1
2

[1 .. n]

is the fact that it also works with arrays and sequences:

1
2
3
4

[|1 .. n |]

{1 .. n}

The more I work with F# the more I wish I could do it for my day job. I'm just looking forward to the day when the rest of the world catches up with the smarts that inform F#.

But my original point was the effective equivalence between the recursive version of the code and the Seq.fold version. I'm not sure that catamorphisms would also apply in the case of a List.reduce but I would be interested to find out.

I've been trying to figure out how to do a Seq.fold version of the tail-call optimized version of those functions which use continuations.

To be pedantic, I'd restrict Brian's claim to structural recursion. For instance, take a discriminated union representing natural numbers:

1

type Nat = Z | S of Nat

Here Z represents zero and S constructs the successor to another natural number. Then the fold operator for this type is:

1
2
3

let rec fold z s = function
| Z -> z
| S n -> s (fold z s n)

Now we can define any function which could have been defined by recursion and case analysis using the fold instead:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let add n = fold n S


let mul n = fold Z (add n)


let fact = fold (S Z, Z) (fun (N, n) -> mul N (S n), S n) >> fst


let toInt = fold 0 ((+) 1)


let one = S Z
let two = S one
let three = S two
let six = fact three
let sixI = six |> toInt

Note: because we're using a unary representation here, don't call fact on anything bigger than four or five, or the resulting value will be a bit annoying to view...

You can also do the same thing with actual ints instead of our discriminated union above, which may be easier to read:

1
2
3
4
5
6
7
8
9
10
11

module Int = begin
  
  let rec fold z s = function
  | 0 -> z
  | n -> s (fold z s (n-1))
  
  let add n = fold n ((+) 1)
  let mul n = fold 0 (add n)
  let fact = fold (1,0) (fun (N,n) -> N*(n+1), n+1) >> fst

end

The key to being able to do this is that we're still conceptually using a structural basis on which we want to

recurse, which allows us to define the fold in a natural way. However, for problems which don't break down nicely using this recursion structure, we will have a tough time using this fold to represent the recursion. For instance, take the following fast exponentiation definition:

1
2
3
4
5
6
7
8

let rec powi n = function
| 0 -> 1
| e ->
    let n' = powi n (e/2)
    if (e%2 = 1) then 
      n' * n' * n
    else
      n' * n'

Even though this is a function defined using recursion on an integral argument, there's no good way to represent this function with our fold because for an argument e we're recursing on (e/2), not (e-1).