Haskell `let` связывания в лямбда-исчислении

Question

Я хочу понять как let привязки работают в Haskell (или, может быть, лямбда-исчисление, если реализация Haskell отличается?)

Я понял из чтения Пишу вам Haskell, что это действительно для одного let связывание.

let x = y in e == (\x -> e) y

Это имеет смысл для меня, поскольку это согласуется с тем, как работают привязки в лямбда-исчислении. Где я запутался, использует несколько let привязки, где одна привязка может ссылаться на привязки выше. Я приведу тривиальный пример.

Оригинальный код:

let times x y = x * y
    square x = times x x
in square 5

Моя догадка при реализации:

(\square times -> square 5) (\x -> times x x) (\x -> x * x)

Кажется, это не работает, потому что times не определяется, когда квадрат называется лямбда-выражением. Однако это может быть решено этой реализацией:

(\square -> square 5) ((\times x -> times x x) (\x -> x * x))

Это правильный способ реализовать это связывание, по крайней мере, в лямбда-исчислении?

Answer 1

times/square Пример может быть выражен в терминах лямбда-функций с использованием scoping:

(\times -> (\square -> square 5)(\x -> times x x))(\x y -> x * y)

Но области видимости недостаточно для рекурсивных или взаимно рекурсивных привязок типа

let ones = 1 : ones in take 5 ones

let even n = n == 0 || odd (abs n - 1)
    odd n  = n /= 0 && even (abs n - 1)
in even 7

В лямбда-исчислении вы можете определить Y-комбинатор для рекурсии как

(\f -> (\x -> f (x x))(\x -> f (x x)))

Это позволяет вам определять функции и значения в терминах самих себя. Эта формулировка не является легальным путаницей из-за ограничений при вводе, но есть способы обойти это.

Использование y-комбинатора позволяет выразить вышеупомянутые привязки, используя лямбда-исчисление:

(\ones -> take 5 ones)((\f -> (\x -> f (x x))(\x -> f (x x)))(\ones -> 1 : ones))

(\evenodd -> evenodd (\x y -> x) 7)((\f -> (\x -> f (x x))(\x -> f (x x)))(\evenodd c -> c (\n -> n == 0 || evenodd (\x y -> y) (abs n - 1)) (\n -> n /= 0 && evenodd (\x y -> x) (abs n - 1)))) 

Answer 2

Обратите внимание, что несколько let привязки могут быть сведены к одному, определяя пару (кортеж, в общем случае). Например, мы можем переписать

let times x y = x * y
    square x = times x x
in square 5

как

let times = \x y -> x * y
    square = \x -> times x x
in square 5

затем

let (times, square) = (\x y -> x * y, \x -> times x x)
in square 5

затем, если хотите,

let pair = (\x y -> x * y, \x -> fst pair x x)
in snd pair 5

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

(\pair -> snd pair 5) (fix (\pair -> (\x y -> x * y, \x -> fst pair x x)))

Обратите внимание, что этот перевод не соответствует алгоритмам вывода типов, которые обрабатывают let особым образом, вводя полиморфизм. Это не важно, если мы заботимся только о динамических аспектах нашей программы.

Answer 3

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

Мы хотим реализовать следующую программу с двумя привязками let:

let times a b = a * b
    square x = times x x
in square 5

Для начала давайте упростим это до сути того, что мы хотим:

square 5

Достаточно просто. Тем не мение, square в этом случае не определено! Ну, мы можем связать это, используя механизм, который обеспечивает нам наш язык - лямбда. Это дает нам (\ square -> square 5) (\x -> times x x), Сейчас square определяется, но его двоюродный брат times нет... ну нам нужна еще одна лямбда! Наша финальная программа должна выглядеть так:

(\times -> (\square -> square 5) (\x -> times x x)) (\a b -> a * b)

Обратите внимание, что (\times -> ...) полностью охватывает наш последний шаг, так что times будет в области, как это связано. Это согласуется с ответом @rampion и сокращается следующим образом:

(\times -> (\square  -> square 5) (\x -> times x x)) (\a b -> a * b) =>
(\square -> square 5) (\x -> (\a b -> a * b) x x)                    =>
(\square -> square 5) (\x -> (\b -> x * b) x)                        => 
(\square -> square 5) (\x -> x * x)                                  => 
(\x -> x * x) 5                                                      =>
5 * 5                                                                => 
25

Если square функция не зависела от timesмы могли бы легко написать (\times square -> ...., Зависимость означает, что мы должны вкладывать эти две среды, одна из которых содержит timesи другой внутри того, что может использовать его определение.

Спасибо за всю твою помощь! Я поражен простотой и мощью лямбда-исчисления.