Как работает Elem с одним элементом

Question

Проблема заключается в упаковке последовательных дубликатов элементов списка в подсписках. Я не понимаю, как elem работает с одним элементом здесь,

Для примера,

pack [1,1,2,2,3,4] 

Тогда x будет 1 и (head (pack xs)) будет 1. Как можно:

1 `elem` 1 

работа когда elem есть тип a -> [a] -> Bool?

Также объясните, пожалуйста, рекурсию.

pack :: (Eq a) => [a] -> [[a]] 
pack [] = [] 
pack [x] = [[x]] 
pack (x:xs) = if x `elem` (head (pack xs)) 
       then (x:(head (pack xs))):(tail (pack xs)) 
       else [x]:(pack xs) 

Answer 1

В вашем примере, x будет 1, но head (pack xs) является не 1. На самом деле, вы можете видеть его тип подписи, тип pack xs должен быть [[Int]] (или по крайней мере [[a]] для какой-то от числа a), а именно список списков цифр, поэтому head (pack xs) имеет тип [Int], а не тип Int. Независимо от его значения, это не может быть 1.

Если это еще не ясно, посмотрите на более короткий пример pack [1,2]. Он будет соответствовать шаблону pack (x:xs) с x=1 и xs=[2], поэтому правая сторона вызова elem будет head (pack [2]). Вы можете проверить, что это эквивалентно head [[2]], который оценивает в [2], и теперь выражение:

1 `elem` [2] 

имеет смысл.

Помните, что хотя head возвращает первый элемент списка, Haskell позволяет списки списков, а первым элементом списка списков является другой список.

Редактировать: Чтобы объяснить рекурсию, давайте рассмотрим полный пример pack [1,1,2]. Каждый раз, когда мы пытаемся оценить pack вызов, мы будем использовать один из шаблонов для pack, которые я пронумерованные:

pack [] = []    -- #1 
pack [x] = [[x]]   -- #2 
pack (x:xs) = if x `elem` (head (pack xs)) -- #3 
       then (x:(head (pack xs))):(tail (pack xs)) 
       else [x]:(pack xs) 

Когда Haskell пытается оценить pack [1,1,2], потому что [1,1,2] эквивалентно (если вы не Посмотрите, пожалуйста, определение оператора : и попробуйте его на нескольких примерах!), он соответствует шаблону № 3 с x=1 и xs=[1,2]. Таким образом, Haskell может оценить это, используя правую сторону шаблона № 3 с этими замещенными значениями для x и xs. Просто чтобы быть совершенно ясно, ОРЗ с этими заменами выглядит следующим образом, который мы называем «выражением (А)»:

if 1 `elem` (head (pack [1,2])) 
then (1:(head (pack [1,2]))):(tail (pack [1,2])) 
else [1]:(pack [1,2]) 

Убедитесь, что вы считаете, что это правильно, прежде чем продолжить! Теперь самая сложная часть оценки этого выражения заключается в том, как оценить pack [1,2], который используется в нескольких местах.Итак, давайте выясним, как Haskell оценивает pack [1,2]. Опять же, потому что [1,2] эквивалентен 1:[2] (проверьте это!), Это соответствует рисунку № 3 с x=1 и xs=[2]. RHS узора № 3 с этими заменами заключается в следующем, что мы будем называть «выражение (B)»:

if 1 `elem` (head (pack [2])) 
then (1:(head (pack [2]))):(tail (pack [2])) 
else [1]:(pack [2]) 

Для оценки экспрессии (B), мы должны выяснить значение pack [2]. На этот раз это выражение соответствует шаблону № 2 с x=2. (На самом деле, он будет соответствовать шаблону № 3 тоже с x=2 и xs=[], но Haskell использует первый шаблон, который соответствует, поэтому он никогда не учитывает эту возможность.) Подставляя x=2 в RHS шаблона № 2, получаем следующее эквивалентное значение для pack [2] , который мы будем называть «выражением (C)», хотя он так короток, что, вероятно, не заслуживает имени.

[[2]] 

Принимая это и подставляя его обратно в выражение (B) выше, мы буквально получаем:

if 1 `elem` (head [[2]]) 
then (1:(head [[2]])):(tail [[2]]) 
else [1]:[[2]] 

Все, что я сделал здесь заменен pack [2] с [[2]] везде он появляется, а затем я удалил некоторые дополнительные круглые скобки, которые не меняли смысла. Условие в операторе if совпадает с 1 `elem` [2], что является ложным, поэтому значение равно [1]:[[2]], которое может быть переписано как [[1],[2]]. (Опять же, проверьте, не видите ли вы почему.) Это конечное значение для выражения (B), и поэтому окончательное значение pack [1,2]. Теперь мы можем подставить это значение в выражение (A), чтобы получить:

if 1 `elem` (head [[1],[2]]) 
then (1:(head [[1],[2]])):(tail [[1],[2]]) 
else [1]:[[1],[2]] 

Теперь, потому что head [[1],[2]] просто [1], условие в if утверждении 1 `elem` [1] что верно, поэтому Haskell оценивает часть даваемой then статья. Это некрасиво, но вы должны быть в состоянии убедить себя, что это значение:

(1:(head [[1],[2]])):(tail [[1],[2]]) 
= (1:[1]):[[2]] 
= [1,1]:[[2]] 
= [[1,1],[2]] 

Это окончательное значение выражения (А), но, конечно, было значение pack [1,1,2], так что вы можете видеть, что все это сработало.

Answer 2

Как уже прокомментировал ци, используя head и tail, как правило, проблематично и скрыто. В вашем примере это также создает гигантскую проблему с производительностью, поскольку на каждом этапе рекурсии вы снова и снова оцениваете pack xs - если только компилятор не выполняет некоторую нетривиальную оптимизацию, это имеет экспоненциальную сложность!

Я бы рекомендовал следующее вместо этого, используя case и охранников:

pack (x:xs) = case pack xs of 
    thisPack : packs 
    | x `elem` thisPack -> (x:thisPack) : packs 
    otherPacks   -> [x] : otherPacks