Частичная оценка и каррирование - PullRequest
Новая
       77

Частичная оценка и каррирование

4 голосов
/ 12 февраля 2011

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

Я знаю, как это работает в следующем примере: 

fun funkyPlus x y = x*x+y;

так скажем, мы передаем аргумент только для x, тогда он эквивалентен следующему: 

fun funkyPlus 3 = (fn x => fn y => x*x+y)3

что в итоге возвращает 

fn y => 9+y

Теперь я пытаюсь применить эту идею к встроенной функции foldl.

Я знаю код для этого: 

fun foldl f b [] = b
   |foldl f b (h::t) = foldl f f(h,b) t.

Мой вопрос таков: что если мы не передадим все аргументы foldl (т.е. мы передадим ему только первый аргумент, который является функцией ('a*'b->'b)). В первом примере, который я привел, было довольно просто увидеть, как работает функция, когда ей передается только один из аргументов. Тем не менее, я не могу понять, как будет работать foldl, если ему передан только один аргумент.

Помощь.

Ответы [ 2 ]

2 голосов
/ 12 февраля 2011

  1. Это не значит, что вы думаете: 

    fun funkyPlus 3 = (fn x => fn y => x*x*y)3

    Он определяет функцию, которая принимает аргумент, который должен быть равен 3, и которая оценивает ее RHS, если она равна 3, и не определена в противном случае. Вы хотите сказать следующее: если мы предоставляем аргумент только для x, мы имеем следующее: 

    funkyPlus 3
→ (fn x => fn y => x*x+y) 3

    и пр.

  2. Во-вторых, в вашем foldl есть ошибка: 

    fun foldl f b [] = b|foldl f b (h::t) = foldl f f(h,b) t;
                                                 ^^^^^
Type clash: expression of type
  'a * 'b
cannot have type
  'c list

    Это потому, что (h,b) анализируется как третий аргумент foldl, а не как аргумент f. Поставьте в скобки это: 

    fun foldl f b [] = b|foldl f b (h::t) = foldl f (f(h,b)) t;
> val ('a, 'b) foldl = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Теперь, перейдя к вашему вопросу, ML может сказать нам, что выражение типа foldl add будет иметь тип int -> int list -> int.

Но в целом это может помочь понять, что применение функции полностью механическое. Если у нас есть эти два определения: 

fun foldl f b [] = b
  | foldl f b (h::t) = foldl f (f(h,b)) t;
add (x,y) = x + y;

тогда var example = foldl add будет эквивалентно этому: 

fun example b [] = b
  | example b (h::t) = example (h::t) (add(h,b)) t;

Все, что было сделано, это то, что add был заменен на f в теле foldl, ничего более (хотя я позволил себе сменить foldl add на example в теле).

1 голос
/ 12 февраля 2011

Первый шаг - превратить ваш набор уравнений верхнего уровня для foldl в лямбда-выражение, которое использует анализ случая, например: 

val rec foldl = fn f => fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl f (f(h,b)) t

Теперь вы можете использовать ту же логику, что и раньше. Взяв в качестве примера функцию fn (x, y) => x * y, мы можем видеть, что 

val prod = foldl (fn (x, y) => x * y)

эквивалентно 

val prod = (fn f => fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl f (f(h,b)) t) (fn (x, y) => x * y)

который бета-уменьшает до 

val prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl (fn (x, y) => x * y) ((fn (x, y) => x * y)(h,b)) t

, бета-версия которого уменьшается до 

val prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl (fn (x, y) => x * y) (h * b) t

Теперь, поскольку мы знаем из нашего первого определения, что prod эквивалентно foldl (fn (x, y) => x * y), мы можем подставить его в его собственное определение: 

val rec prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => prod (h * b) t

Затем мы можем мысленно преобразовать это обратно в функцию, определяемую уравнениями, если нам нравится: 

fun prod b [] = b
  | prod b (h::t) = prod (h * b) t

Это то, что вы ожидаете, верно?

...