Простые функции Haskell в стиле point-free

Я пытаюсь понять, как преобразовать функции в точечную нотацию в Haskell. Я видел этот пример, но это сложнее, чем то, что я ищу. Я чувствую, что понимаю логику, но когда я пытаюсь выполнить некоторые простые примеры в коде, я получаю ошибки компиляции. Я хочу попытаться написать эту функцию в стиле point-free:

f x = 5 + 8/x, который я изменил как f x = (+) 5 $ (/) 8 x

Итак, я подумал, что это может быть примерно так:

f = (+) 5 $ (/) 8

но когда я запускаю это в ghci, я получаю это сообщение:

No instance for (Num (a0 -> a0))
  arising from the literal `5' at Test.hs:3:9
Possible fix: add an instance declaration for (Num (a0 -> a0))
In the first argument of `(+)', namely `5'
In the first argument of `($)', namely `(+) 5'
In the expression: (+) 5 $ (/) 8
Failed, modules loaded: none.

Я не понимаю сообщение "Нет экземпляра для...". Что мне нужно сделать, чтобы написать эту функцию в стиле point-free?

Ответы

Ответ 1

$ имеет очень низкий приоритет. Итак, f x = (+) 5 $ (/) 8 x на самом деле означает f x = (+) 5 $ ((/) 8 x). Вместо этого перепишите это как

f x = (+) 5 ( (/) 8 x)
f x = ((+) 5) ( ((/) 8) x)
f x = ((+) 5) .  ( ((/) 8) ) x
f = ((+) 5) . ( (/) 8 )
f = (5+) . (8/)

Последнее выражение имеет смысл: f - это композиция из двух операций, сначала разделите 8 на то, что у вас есть, а затем добавьте 5 к результату. Помните, g.h означает "применить h, а затем применить g к результату этого".

Ответ 2

Программа "pointfree" может быть установлена ​​с помощью cabal install pointfree и показывает вам, как писать выражение в стиле pointfree. Например:

$ pointfree "f x = 5 + 8/x"
f = (5 +) . (8 /)

Объяснение этого преобразования:

  • Вы можете использовать "разделы" для функций infix/operator. (a +) == \b -> a + b и (+ a) == \b -> b + a
  • Функция . принимает результат второго параметра, который является функцией с одним аргументом и применяет его к первому аргументу.

Ответ 3

Преобразование из лямбда-исчисления (которое Haskell является вариантом) терминов SKI (абсолютно свободные функции, используя только const (K), id ( I) и <*> ( S)) можно выполнить со следующими простыми правилами:

  • \x -> x переводится на id;
  • \x -> y без x, встречающегося в y, переводится в const y;
  • \x -> f g переводится на f' <*> g' где
    • f' - это перевод \x -> f и
    • g' является переводом \x -> g.

Теперь вы можете задаться вопросом, куда входит .. Существует специальный случай последнего перевода: если f не имеет свободных вхождений x, то \x -> f g переводится на const f <*> (\x -> g), который равен f . (\x -> g).

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

f = \x -> ((+) 5) (((/) 8) x) = -- by the special-case (.) rule
((+) 5) . (\x -> (((/) 8) x)) = -- by eta-reduction ((\x -> f x) = f)
((+) 5) . ((/) 8)

Эта-редукция не нужна для завершения перевода, но без нее мы получим что-то более беспорядочное. Например, последний шаг привел бы вместо ((+) 5) . ((/) 8) . id.

Ответ 4

Ты был очень близок. Позвольте мне добавить еще один $ для иллюстрации:

f x = (+) 5 $ (/) 8 $ x

Должно быть ясно, что выражение (+) 5 - это функция, которая принимает один числовой ввод и производит числовой вывод. То же самое относится к выражению (/) 8. Таким образом, вы берете любое число, которое вводится, x и сначала применяете функцию (/) 8 ", а затем применяете функцию (+) 5".

Всякий раз, когда у вас есть цепочка функций, разделенных $, вы можете заменить все, кроме самого правого, на . Значение, если у вас есть a $ b $ c $ d, это эквивалентно a . b . c $ d.

f x = (+) 5 . (/) 8 $ x

На этом этапе вместо этого удалим $ и в скобках.

f x = ((+) 5 . (/) 8) x

Теперь должно быть ясно, что вы можете удалить трейлинг x с обеих сторон:

f = (+) 5 . (/) 8

Это основная идея. Если у вас f x = expr x, вы можете "eta уменьшить" его до f = expr. Чтобы создать код без кода, вам нужно просто узнать, как большая функция состоит из меньших функций. Частичное применение иногда необходимо для точечного свободного кода (как в этом случае, (+) 5 и (/) 8 частично применяются). Программа "pointfree" очень полезна, когда вы не хотите об этом думать; Lambdabot на канале #haskell irc использует эту программу в качестве плагина, поэтому вам даже не нужно устанавливать ее самостоятельно; просто спросите:

<DanBurton> @pl let f x = 5 + 8 / x in f
<lambdabot> (5 +) . (8 /)