Результат оценки функции

Question

Я пытаюсь оценить вручную fc [f1, f2] (\x -> 2) 3 но я не понимаю, как сопоставить три параметра: [f1, f2], (\x -> 2) и 3 с определением функции, любая помощь?

Определение функции:

fc xss = \f -> let ope x y = x . f . y in foldr1 ope xss

f1, f2 :: Int -> Bool
f1 x = (x `mod` 3) == 0
f2 x = (x `mod` 5) == 0

Спасибо,
Себастьян.

Answer 1

Ну, сначала сделаем некоторое η- расширение

fc :: [a->b] -> (b->a) -> a->b
fc xss f = let ope x y = x . f . y in \q -> foldr1 ope xss q
 fc xss f q = let ope x y = x . f . y in foldr1 ope xss q

Тогда возможно встроить let

 fc xss f q = foldr1 (\x y -> x . f . y) xss q

Ты можешь написать [f1, f2] как (==0).(`mod`3) : (==0).(`mod`5) : [],

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

Answer 2

Помните, что все функции в Haskell являются функциями одного аргумента для одного результата.

Выражения как func arg1 arg2 arg3 может выглядеть как функция, примененная к 3 аргументам, но это действительно ((func arg1) arg2) arg3), где func arg1 приводит к новой функции, которая применяется к arg2 чтобы получить 3-ю функцию, которая наконец применяется к arg3,

Определения как func arg1 arg2 arg3 = ... являются синтаксическим сахаром для эквивалентных определений, таких как func arg1 = \arg2 -> (\arg3 -> ... )где мы явно выписали промежуточные функции, созданные по пути.

Так fc [f1, f2] (\x -> 2) 3 применяет fc в [f1, f2]и затем применяя результат этого. Понятно как подать заявку fc с одним аргументом (потому что его определение имеет один аргумент), поэтому давайте просто сделаем первый шаг и посмотрим, что мы получим.

fc [f1, f2] = \f -> let ope x y = x . f . y in foldr1 ope [f1, f2]

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

(\f -> let ope x y = x . f . y in foldr1 ope [f1, f2]) (\x -> 2) 3

Теперь снова у нас есть функция (\f -> ...) применяется к одному аргументу (\x -> 2). Результат этого применяется снова (к 3), но об этом мы будем беспокоиться позже.

(\f -> let ope x y = x . f . y in foldr1 ope [f1, f2]) (\x -> 2)
  = let ope x y = x . (\x -> 2) . y in foldr1 ope [f1, f2]

Так что это дало нам выражение foldr1 ope [f1, f2]с дополнительным определением ope от let; мы могли бы заменить это, если мы хотим, но я позволю имени ope остаться в качестве подставки. Подставляя это обратно (помня, что мы определили ope):

(foldr1 ope [f1, f2]) 3

foldr эквивалентно следующему:

foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)

Таким образом, мы можем расширить foldr1 выражение, помня, что [f1, f2] это просто еще один способ написания f1:[f2]:

foldr1 ope (f1:[f2]) = ope f1 (foldr1 ope [f2])
                     = ope f1 f2

Подставляя это обратно, мы получаем:

ope f1 f2 3

Теперь давайте воспользуемся определением для ope, которое мы отложили: ope x y = x . (\x -> 2) . y (опять же, мы могли бы заменить это раньше, но это просто означало бы копировать определение везде, где мы написали ope выше). Вспоминая это ope действительно является функцией одного аргумента, хотя нам было позволено определить его так, как будто для удобства он имеет два аргумента, давайте применим его по одному аргументу за раз:

ope f1 = \y -> f1 . (\x -> 2) . y

Итак, теперь у нас есть:

(\y -> f1 . (\x -> 2) . y) f2 3

Применение лямбды дает нам:

(f1 . (\x -> 2) . f2) 3

И, наконец, мы обнаружили, что 3 это аргумент в пользу композиции "конвейер" f1 . (\x -> 2) . f2, Я остановлюсь здесь, но вы могли бы использовать определение . расширить это дальше и выяснить, что конечная функция 3 передается в.

Итак, 3 значения [f1, f2], (\x -> 2), а также 3 из вашего исходного выражения не нужно было сопоставлять непосредственно с аргументами, определенными для fcпотому что они были не все аргументы этому вообще. [f1, f2] был аргумент fc, (\x -> 2) был аргумент, который был тривиально вычислен fc [f1, f2] (чтобы вы могли думать об этом как о "втором аргументе" fc если ты хочешь; было бы очень легко переписать уравнение для fc так что это появляется прямо как аргумент). 3 с другой стороны, он не был аргументом функции, близкой к написанной непосредственно в источнике, в итоге он был передан функции, вычисленной выражением fc [f1, f2] (\x -> 2),