Преобразование этого куска кода из Haskell в SML (катаморфизм / сгиб) - PullRequest
Новая
       110

Преобразование этого куска кода из Haskell в SML (катаморфизм / сгиб)

2 голосов
/ 30 апреля 2020

Я пытаюсь перевести этот фрагмент кода из 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>))

Я не совсем понимаю, в чем здесь проблема. Любая помощь будет оценена!

1 Ответ

1 голос
/ 30 апреля 2020

Вы получаете сообщение об ошибке 

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, вероятно, не совсем то, что вы хотите. Я не совсем понимаю, как здесь работает вывод типов, хотя кто-то с большим опытом, чем я, мог бы прокомментировать, но, насколько я понимаю, у вас возникла проблема, связанная с тем, что вы хотите быть полиморфной c функцией внутри не -экспансивное выражение (выражение let) и, таким образом, вызывает ограничение значения SML .

Я думаю, что вы можете еще больше упростить свой код, просто сопоставив шаблон в списке, вместо привязки fun в let, например, 

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