将这段代码从Haskell转换为SML（同形/折叠）

Question

我正在尝试将这段代码从Haskell转换为SML，它将产生一个高阶函数（众所周知的文件夹）

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)

因此，如果我们要创建一个新函数prod，它将为我们提供列表中所有元素的乘积，我们可以通过以下方式创建：

prod = list_cata (1, (*))

这是我到目前为止的内容：

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)

虽然list_cata函数编译时，是产品给了我错误。到目前为止，我得到的错误是：

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

我不太了解这里的问题。任何帮助，将不胜感激！

Answer 1

您收到错误消息

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

由于行

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

具体来说，您要传递的元组的第二个元素是[* ty] * [* ty] -> [* ty]。相反，您期望的类型是'a -> 'b -> 'b的实例。因此，出现这种情况是因为您在需要使用咖喱函数的地方使用了非咖喱函数。

假设然后我们修改为

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

如果执行此操作，您将得到prod的一种非常奇怪的类型，可能不是您想要的。我对类型推断的工作方式尚不十分清楚，尽管经验丰富的人超出了我的评论范围，但据我了解，您最终遇到了一个问题，该问题是您想在非扩展表达式中成为多态函数（let表达式），从而调用SML的value restriction。

我认为您可以通过仅对列表进行模式匹配而不是像这样在fun中绑定let来进一步简化代码

fun 'a 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