Описание concatMap

Question

Привет, народ StackOverflow!

Я начал работать с Haskell и наткнулся на функцию concatMap. Поскольку я совершенно новый для этого языка, у меня есть некоторые проблемы с пониманием следующего кода (source):

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = accum (f x) where 
     accum [] = cmap xs 
     accum (y : ys) = y : accum ys 

Насколько я понимаю функцию concatMap принимает в качестве аргумента f который является функцией.

Но как мы можем установить функцию, равную другой? Установили ли мы результат f, равный cmap, или мы используем cmap в качестве параметра для f?

Любая помощь будет высоко ценится,

Спасибо заранее!

Answer 1

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

accum [] = cmap xs 
accum (y : ys) = y : accum ys 

Функция выше, когда список ввода пуста возвращается cmap xs, в противном случае на y:ys излучает y в качестве первого выходного элемента, а затем переходит к выходу accum xs, рекурсивно.

Следовательно, accum zs будет просто выводить все элементы в zs, а затем, после этого, продолжить с cmap xs. Мы можем переписать это как:

accum zs = zs ++ cmap xs 

где ++ является список конкатенации.

Затем мы можем переписать весь код следующим образом, соответственно:

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = f x ++ cmap xs 

Далее мы можем переписать как

concatMap f [] = [] 
concatMap f (x : xs) = f x ++ concatMap f xs 

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

concatMap f [x1,x2,...,xn] = 
    f x1 ++ f x2 ++ ... ++ f xn ++ [] 

Таким образом, мы можем увидеть, что concatMap делает. Он применяет f к каждому элементу списка, и для каждого элемента списка f должен возвращать список. Затем все такие списки объединяются.

Например: ответ

concatMap (\x -> [1..x]) [3,1,2] = 
    [1,2,3] ++ [1] ++ [1,2] = 
    [1,2,3,1,1,2] 

Answer 2

й Рассказывается concatMap работы, поэтому я остановлюсь именно на одном из ваших сомнений:

Но как мы можем установить функцию, равную другой?

Функция в Haskell - это значение, как и любое другое.

GHCi> foo = "foo" 

Это определение foo, который бывает строка:

GHCi> :t foo 
foo :: [Char] 
GHCi> putStrLn foo 
foo 

Таким же образом ...

GHCi> add = (+) 

... это определение add, который является функцией:

GHCi> :t add 
add :: Num a => a -> a -> a 
GHCi> add 2 3 
5 

В приведенном выше определении, чтобы подчеркнуть, что я просто определял значение, я не написал ни одного из параметров add явно. Это прекрасно, чтобы сделать это, хотя:

GHCi> add x y = (+) x y 

(. Обратите внимание, что x + y, который, как мы обычно бы написать правую из приведенного выше определения, просто удобно альтернативный синтаксис для (+) x y)

Другой способ написания определение имеет преимущество частичного применения упомянуть только первый параметр:

GHCi> add x = (+) x 

Мы также можем, только для ради этого (и, возможно, выяснить, что происходит), переместите (+) x в отдельное определение в где-п ...

GHCi> :{ 
GHCi| add x = plusX 
GHCi|  where 
GHCi|  plusX = (+) x 
GHCi| :} 

... и записать второй параметр явно снова:

GHCi> :{ 
GHCi| add x = plusX 
GHCi|  where 
GHCi|  plusX y = (+) x y 
GHCi| :} 

plusX - это функция, которая принимает аргумент и добавляет его в x. add - это функция, которая принимает аргумент x и возвращает функцию plusX, соответствующую этому x. Именно эта вторая функция принимает второй аргумент add, когда мы делаем add 2 3 (что, кстати, эквивалентно (add 2) 3).

Теперь сравните выше с concatMap определения:

concatMap f = cmap where 
    cmap [] = [] 
    cmap (x : xs) = accum (f x) where 
     accum [] = cmap xs 
     accum (y : ys) = y : accum ys 

Определения изложены аналогичным образом. cmap - это функция, которая принимает список и использует f, аргумент concatMap, чтобы получить результат от него, точно так же plusX использовал аргумент xadd.

Итак, подведем итог:

настраиваете мы результат е равно CMAP, или мы используем CMap в качестве параметра для е?

Ни то, ни другое. Мы используем f для определения cmap, который затем используется для определения concatMap в целом.