Применение функции Haskell и каррирование

Question

Я всегда заинтересован в изучении новых языков, факт, который держит меня в напряжении и делает меня (я считаю) лучшим программистом. Мои попытки покорить Хаскелл приходили и уходили - вдвое больше - и я решил, что пришло время попробовать еще раз. 3-й раз это очарование, верно?

Нет. Я перечитываю свои старые заметки ... и разочаровываюсь: - (

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

[int] -> [[int]]

На самом деле это общая проблема, поэтому замена 'int' выше на 'a' все равно будет применяться.

Из моих заметок:

Сначала я пишу код самостоятельно, мне это удается. Ура!

Я отправляю свое решение моему хорошему другу - гуру Хаскелла, оно обычно помогает учиться у гуру - и он посылает мне это, как мне говорят, "выражает истинную силу языка, использование общих средств кодировать ваши потребности ". Все для этого, я недавно выпил kool-aid, поехали:

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

Хм. Давайте разберем это:

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

Хорошо, пока все хорошо. Мне потребовалась минута, чтобы понять вторую строку «ins», но хорошо: Он помещает 1-й аргумент во все возможные позиции в списке. Круто.

Теперь, чтобы понять foldr и concatMap. в "Реальном мире Хаскелла" ТОЧКА была объяснена ...

(f . g) x

... как еще один синтаксис для ...

f (g x) 

И в коде, который послал гуру, DOT использовался из Foldr, с функцией «ins» как «свертывание» фальца:

*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

ОК, так как я хочу понять, как DOT используется гуру, я пробую эквивалентное выражение в соответствии с определением DOT, (f. G) x = f (g x) ...

*Main> concatMap (ins 1 [[2,3]])

<interactive>:1:11:
     Couldn't match expected type `a -> [b]'
            against inferred type `[[[t]]]'
     In the first argument of `concatMap', namely `(ins 1 [[2, 3]])'
     In the expression: concatMap (ins 1 [[2, 3]])
     In the definition of `it': it = concatMap (ins 1 [[2, 3]])

Что!?! Зачем? Хорошо, я проверяю сигнатуру concatMap и нахожу, что ей нужны лямбда и список, но это просто человеческое мышление; как справится GHC? Согласно определению DOT выше ...

(f.g)x = f(g x), 

... то, что я сделал, было действительным, по замене:

(concatMap . ins) x y = concatMap (ins x y)

царапающая головка ...

*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

Итак ... Объяснение DOT было очевидно слишком упрощенно ... DOT должен быть достаточно умным, чтобы понять что мы на самом деле хотели, чтобы «ины» вырвались и «съели» первое аргумент - таким образом становясь функцией, которая хочет работать только с [t] (и «чередуйте» их с «1» во всех возможных положениях).

Но где это было указано? Как GHC знал, что делать это, когда мы вызывали:

*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

Подпись "ins" как-то передавала эту политику "съесть мой первый аргумент"?

*Main> :info ins
ins :: t -> [t] -> [[t]]        -- Defined at b.hs:1:0-2

Я не вижу ничего особенного - «ins» - это функция, которая принимает «t», список 't', и приступает к созданию списка со всеми "interspersals". Ничего о "съешь свой первый аргумент и убери его".

Так что ... я сбит с толку. Я понимаю (после часа просмотра кода!) Что происходит, но ... Бог всемогущий ... Возможно, GHC пытается выяснить, сколько аргументов он может "снять"?

  let's try with no argument "curried" into "ins",
  oh gosh, boom, 
  let's try with one argument "curried" into "ins",
  yep, works,
  that must be it, proceed)

Опять - yikes ...

И поскольку я всегда сравниваю языки, которые я изучаю, с тем, что я уже знаю, как будет выглядеть «ins» в Python?

a=[2,3]
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]

[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

Если честно, теперь ... что проще?

Я имею в виду, я знаю, что я новичок в Haskell, но я чувствую себя идиотом ... Глядя на 4 строки кода в течение часа и заканчивая тем, что компилятор ... пробует различные интерпретации, пока не найдет что-то, что «щелкает»?

Цитата из смертоносного оружия: "Я слишком стар для этого" ...

Answer 1

(f . g) x = f (g x)

Это правда.Из этого вы пришли к выводу, что

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

также должно быть правдой, но это не так.На самом деле, верно следующее:

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

, что не одно и то же.

Почему это так?Ну, (f . g) x y - это то же самое, что и ((f . g) x) y, и, поскольку мы знаем, что (f . g) x = f (g x), мы можем уменьшить его до (f (g x)) y, что опять же равно f (g x) y.

Так что (concatMap . ins) 1 [[2,3]] эквивалентнодо concatMap (ins 1) [[2,3]].Здесь не происходит никакой магии.

Другой способ подойти к этому - через типы:

. имеет тип (b -> c) -> (a -> b) -> a -> c, concatMap имеет тип (x -> [y]) -> [x] -> [y],ins имеет тип t -> [t] -> [[t]].Поэтому, если мы используем concatMap в качестве аргумента b -> c и ins в качестве аргумента a -> b, то a становится t, b становится [t] -> [[t]] и c становится [[t]] -> [[t]] (сx = [t] и y = [t]).

Таким образом, тип concatMap . ins равен t -> [[t]] -> [[t]], что означает, что функция принимает список any и список списков (whatevers)) и возвращает список списков (одного типа).

Answer 2

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

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

Он просто создает новую функцию, которая применяет g к аргументу, применяет f к результату и возвращает результат применения f.

Итак, (concatMap . ins) 1 [[2, 3]] говорит: создайте функцию concatMap . ins и примените ее к аргументам 1 и [[2, 3]]. Когда вы делаете concatMap (ins 1 [[2,3]]), который вы вместо этого говорите, примените функцию concatMap к результату применения ins к 1 и [[2, 3]] - совершенно другому, как вы поняли из ужасного сообщения об ошибке Haskell.

ОБНОВЛЕНИЕ: чтобы подчеркнуть это еще больше. Вы сказали, что (f . g) x был другим синтаксисом для f (g x). Это неправильно ! . - это просто функция, поскольку функции могут иметь не алфавитно-цифровые имена (>><, .. и т. Д. Также могут быть именами функций).

Answer 3

Вы задумывались над этой проблемой.Вы можете решить все это с помощью простых эквалайзеров.Давайте попробуем это с нуля:

permute = foldr (concatMap . ins) [[]]

Это можно легко преобразовать в:

permute lst = foldr (concatMap . ins) [[]] lst

concatMap можно определить как:

concatMap f lst = concat (map f lst)

Способfoldr работает со списком, который (например):

-- let lst = [x, y, z]
foldr f init lst
= foldr f init [x, y, z]
= foldr f init (x : y : z : [])
= f x (f y (f z init))

Итак, что-то вроде

permute [1, 2, 3]

становится:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))

Давайте работать черезпервое выражение:

(concatMap . ins) 3 [[]]
= (\x -> concatMap (ins x)) 3 [[]]  -- definition of (.)
= (concatMap (ins 3)) [[]]
= concatMap (ins 3) [[]]     -- parens are unnecessary
= concat (map (ins 3) [[]])  -- definition of concatMap

сейчас ins 3 [] == [3], поэтому

map (ins 3) [[]] == (ins 3 []) : []  -- definition of map
= [3] : []
= [[3]]

Итак, наше первоначальное выражение становится:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]]

Давайте проработаем

(concatMap . ins) 2 [[3]]
= (\x -> concatMap (ins x)) 2 [[3]]
= (concatMap (ins 2)) [[3]]
= concatMap (ins 2) [[3]]     -- parens are unnecessary
= concat (map (ins 2) [[3]])  -- definition of concatMap
= concat (ins 2 [3] : [])
= concat ([[2, 3], [3, 2]] : [])
= concat [[[2, 3], [3, 2]]]
= [[2, 3], [3, 2]]

Итак, наше первоначальное выражение становится:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 [[2, 3], [3, 2]]
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]]
= concatMap (ins 1) [[2, 3], [3, 2]]
= concat (map (ins 1) [[2, 3], [3, 2]])
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
          [[1, 3, 2], [3, 1, 2], [3, 2, 1]]]  -- defn of ins
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
   [1, 3, 2], [3, 1, 2], [3, 2, 1]]

Ничего волшебного здесь нет.Я думаю, что вы, возможно, были сбиты с толку, потому что легко предположить, что concatMap = concat . map, но это не так.Точно так же это может показаться concatMap f = concat . (map f), но это тоже не так.Эквациональное рассуждение покажет вам, почему.