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

Question

我正在尝试将这段代码从 Haskell 转换为 SML，它将产生高阶函数（众所周知的 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)

因此，如果我们想创建一个新函数 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 函数编译它是 prod 给我的错误。到目前为止我得到的错误是：

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。

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

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

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

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

haskell

functional-programming

sml

smlnj

fold