Converting this piece of code from Haskell to SML (catamorphism / fold)

Question

I'm trying to translate this piece of code from Haskell to SML that will produce a higher-order function (the well-known foldr)

type List_alg x u = (u, x->u->u)
list_cata :: List_alg x u -> [x] -> u list_cata (a,f) = cata where
  cata[] =a
  cata (x:l) = f x (cata l)

So if we want to create a new function prod that will give us a product of all elements in the list we can create by:

prod = list_cata (1, (*))

Here is what I have so far:

type ('a, 'b) List_alg = 'b * ('a -> 'b -> 'b)

fun list_cata (a, f) List_alg: 'a list -> 'b = 
  let
  fun cata (xs: 'a list) : 'b  = 
      case xs of
      [] => a
    | x::xs => f x (cata xs)
  in
    cata
  end

val prod = list_cata (1, fn (x,y) => x*y)

While the list_cata function compiles it's the prod that's giving me the error. The errors so far I get are:

Error: operator and operand do not agree [overload conflict]
  operator domain: [int ty] * ([* ty] * [* ty] -> [int ty] -> [int ty])
  operand:         [int ty] * ([* ty] * [* ty] -> [* ty])
  in expression:
    list_cata (1,(fn (<pat>,<pat>) => <exp> * <exp>))

I don't quite understand what is the problem here. Any help would be appreciated!

Answer 1

You're getting the error message

Error: operator and operand do not agree [overload conflict]
  operator domain: [int ty] * ([* ty] * [* ty] -> [int ty] -> [int ty])
  operand:         [int ty] * ([* ty] * [* ty] -> [* ty])
  in expression:
    list_cata (1,(fn (<pat>,<pat>) => <exp> * <exp>))

because of the line

val prod = list_cata (1, fn (x,y) => x*y)

Specifically, the second element of the tuple you're passing is of, speaking loosely, type [* ty] * [* ty] -> [* ty]. In contrast you're expecting a type which is an instance of 'a -> 'b -> 'b here. Thus, this arises because you're using an uncurried function where you want a curried one.

Suppose then we revise to

type ('a, 'b) List_alg = 'b * ('a -> 'b -> 'b)

fun list_cata (a, f) List_alg: 'a list -> 'b = 
  let
  fun cata (xs: 'a list) : 'b  = 
      case xs of
      [] => a
    | x::xs => f x (cata xs)
  in
    cata
  end

fun curry f a b = f (a, b)
val prod = list_cata (1, curry op*) (* like ( * ) in haskell *)

If you do this, you'll get a rather strange type for prod, probably not quite what you want. I'm not quite clear on how the type inference works here, although someone with more experience than I could comment, but to my understanding you end up with an issue having what you want to be a polymorphic function inside of a non-expansive expression (a let expression) and thus invoke SML's value restriction.

I think you can simplify your code further by just pattern matching on the list instead of having a fun binding in a let like so

fun ('a, 'b) list_cata (f : 'a -> 'b -> 'b) (z : 'b) ([ ] : 'a list) : 'b = z
           | list_cata f z (x::xs) = f x (list_cata f z xs)

fun curry f a b = f (a, b)
val prod = list_cata (curry op*) 1