Карри 3 аргумента в Хаскеле

Question

У меня проблемы с каррированием функции для удаления трех аргументов в Haskell.

Отказ от ответственности: не Курсовая работа, мне задали этот вопрос кто-то, кто боролся с этим сегодня, и это беспокоило меня.

Нам были предоставлены пользовательские типы / функции (могут помнить только типы)

type MyThing
  = (Char, String)
type MyThings
  = [MyThing]

funcA :: MyThings -> String -> String
funcB :: MyThings -> String -> Int -> String

Мы начали с:

funcB as str n = iterate (funcA as) str !! n

И уменьшил это следующим образом:

funcB as str n = iterate (funcA as) str !! n
funcB as str = (!!) . (iterate (funcA as)) str
funcB as = (!!) . (iterate (funcA as))
funcB as = (!!) . (iterate . funcA) as

Затем застрял. Мы просто не можем понять, как избежать использования последнего аргумента. Я знаю, что видел подобную ситуацию где-то раньше, и было решение.

Надеясь на то, что гений Хаскелла может указать, почему я идиот...

Answer 1

Все, что вам нужно здесь, это следующие три "закона" операторских разделов:

(a `op` b) = (a `op`) b = (`op` b) a = op a b
          (1)          (2)          (3)

так что операнд переходит в свободный слот рядом с оператором.

За (.) это означает, что: (a . b) = (a .) b = (. b) a = (.) a b, Так,

f (g x) y !! n      
= (!!) (f (g x) y) n              by (3) 
= ((!!) . f (g x)) y n
= ((!!) . (f . g) x) y n
= ((!!) .) ((f . g) x) y n        by (1)
= (((!!) .) . (f . g)) x y n
= (((!!) .) . f . g) x y n

Вы должны выполнять столько бессмысленных преобразований, сколько вам удобно, чтобы полученное выражение все еще было читабельным для вас - и фактически более четким, чем оригинал. Инструмент "pointfree" может иногда давать нечитаемые результаты.

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

((a .) . b) x y = (a .) (b x) y = (a . b x) y = a (b x y) это общий шаблон, который вы быстро научитесь распознавать сразу. Таким образом, приведенное выше выражение может быть прочитано довольно легко, как

(!!) ((f . g) x y) n = f (g x) y !! n

учитывая, что (.) ассоциативен:

(a . b . c) = ((a . b) . c) = (a . (b . c))

Answer 2

funcB = ((!!) .) . iterate . funcA

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

Вы действительно можете сделать это автоматически с pointfree. Смотрите страницу HaskellWiki

Как говорится в github readme, после установки вы можете редактировать ghci.conf или же .ghci файл со строкой

:def pf \str -> return $ ":! pointfree \"" ++ str ++ "\""

а затем в ghci, когда вы печатаете

:pf funcB as = (!!) . (iterate . funcA) as

или даже

:pf funcB as str n = iterate (funcA as) str !! n

ты получаешь

funcB = ((!!) .) . iterate . funcA

Answer 3

Ключевое наблюдение для меня заключается в том, что инфиксные операторы могут быть написаны префиксом:

funcB as = (!!) . (iterate . funcA) as
funcB as = (.) (!!) ((iterate . funcA) as)

Как только вы попали сюда, у вас есть половина шансов узнать, что это композиция, с (.) (!!) в качестве первого аргумента и iterate . funcA в качестве второго аргумента:

funcB as = (  ((.) (!!)) . (iterate . funcA)  ) as

Теперь понятно, как это упростить; после этого, есть много эстетических выборов о том, как написать это. Например, мы можем наблюдать, что (.) является ассоциативным, и поэтому мы можем отбросить некоторые скобки; аналогично, мы можем использовать операторские секции для объединения неприглядных ((.) (!!)) если вы думаете, что таким образом это более читабельно.

funcB = (  ((.) (!!)) . (iterate . funcA)  )
funcB = (.) (!!) . iterate . funcA -- uncontroversial parenthesis removal
funcB = ((!!) .) . iterate . funcA -- possibly controversial section rewrite

Кстати, я не думаю, что начало вашего вывода правильное. Вы пришли к правильному выводу, но через неправильные средние шаги. Исправлено, это должно выглядеть так:

funcB as str n = iterate (funcA as) str !! n
funcB as str n = (!!) (iterate (funcA as) str) n
funcB as str = (!!) (iterate (funcA as) str)
funcB as = (!!) . iterate (funcA as)