Haskell (:) и (++) различия

Question

Я прошу прощения за такой вопрос. Я не слишком уверен в разнице операторов : и ++ в Haskell.

x:y:[] = [x,y]  

также

[x] ++ [y] = [x,y]

что касается обратной функции, которая возникла у меня для этого вопроса,

reverse ::[a]->[a]
reverse [] = []
reverse (x:xs) = reverse(xs)++[x]

Почему не работает следующее?

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

дает ошибку типа.

Answer 1

Оператор : известен как оператор "cons" и используется для добавления элемента head к списку. Таким образом, [] является списком, а x:[] предшествует x пустому списку, составляющему список [x]. Если вы затем минуете y:[x], вы получите список [y, x], который совпадает с y:x:[].

Оператор ++ - это оператор объединения списков, который принимает два списка в качестве операндов и «объединяет» их в один список. Поэтому, если у вас есть список [x] и список [y], вы можете объединить их следующим образом: [x]++[y], чтобы получить [x, y].

Обратите внимание, что : принимает элемент и список, а ++ - два списка.

Что касается вашего кода, который не работает.

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

Функция реверса оценивает список. Поскольку оператор : не принимает список в качестве первого аргумента, то reverse(xs):x недопустим. Но reverse(xs)++[x] действителен.

Answer 2

: помещает элемент в список.

++ добавляет два списка.

Первый имеет тип

a -> [a] -> [a]

тогда как последний имеет тип

[a] -> [a] -> [a]

Answer 3

Конкатенация с (++)

Может быть, я думаю углубиться в это, но, насколько я понимаю, если попытаться объединить списки, использующие (++), например:

[1, 2, 3] ++ [4, 5]

(++) должен пройти весь левый список. Взгляните на код (++) тем более понятно.

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Таким образом, было бы желательно избегать использования (++), так как при каждом вызове reverse(xs)++[x] список становится больше (или меньше в зависимости на точку зрения. В любом случае, программа просто должна пройти другую список с каждым звонком)

Пример:

Допустим, я реализую реверс, как предложено через конкатенацию.

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]

Изменение списка [1, 2, 3, 4] будет выглядеть примерно так:

reversex [1, 2, 3, 4]
reversex [2, 3, 4]               ++ [1]
reversex [3, 4]           ++ [2] ++ [1]
reversex [4]       ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
         [] ++ [4] ++ [3] ++ [2] ++ [1]
         [4]       ++ [3] ++ [2] ++ [1]
         [4, 3]           ++ [2] ++ [1]
         [4, 3, 2]               ++ [1]
         [4, 3, 2, 1]

Хвостовая рекурсия с использованием оператора cons (:) !!!

Один из способов обработки стеков вызовов - это добавление аккумулятора . (не всегда возможно просто добавить аккумулятор. Но большинство рекурсивные функции, с которыми имеешь дело, являются примитивно-рекурсивными и могут быть преобразованным в хвостовые рекурсивные функции .)

С помощью аккумулятора можно сделать этот пример работать, используя оператор "против" (:). Аккумулятор - ys в моем примере - накапливает текущий результат и передается в качестве параметра. Благодаря аккумулятору мы теперь можем использовать оператор cons для накопления результата путем добавления глава нашего первоначального списка каждый раз.

reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys     = ys

Здесь нужно отметить одну вещь.

Аккумулятор является дополнительным аргументом. Я не знаю, если Хаскелл предоставляет параметры по умолчанию, но в этом случае было бы неплохо, потому что вы всегда вызываете эту функцию с пустым списком как аккумулятор вроде так: reverse' [1, 2, 3, 4] []

Есть много литературы о хвостовой рекурсии, и я уверен, что есть много похожих вопросов на StackExchange / StackOverflow . Пожалуйста, исправьте меня, если вы обнаружите какие-либо ошибки.

С уважением,

РЕДАКТИРОВАТЬ 1 :

Уилл Несс указал несколько ссылок на действительно хорошие ответы для тех из вас, кто интересуется:

• Почему списки различий более эффективны, чем обычная конкатенация?
• Низкая производительность Haskell при (++)

РЕДАКТИРОВАТЬ 2 :

Ok. Благодаря dFeuer и его исправлениям, я думаю, что понимаю Haskell немного лучше.

1. $! выше моего понимания. Во всех моих тестах это казалось усугубить ситуацию.

2.Как dFeuer указал: Thunk, представляющий применение от (:) до x и y, семантически идентичен x:y, но занимает больше памяти. Так что это специально для оператора минусов (и ленивые конструкторы), и нет необходимости форсировать события.

3.Если я вместо этого суммирую целые числа в списке, используя очень похожую функцию, строгая оценка через BangPatterns или функцию seq предотвратит слишком большой рост стека при правильном использовании. e.g.:

sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y      = y

Обратите внимание на удар перед y. Я попробовал это в GHCI, и это занимает меньше памяти.

Answer 4

cons имеет тенденцию быть конструктором типов, а не оператором.пример здесь : можно использовать в let..in.. выражении, но ++ не

let x : xs = [1, 2, 3] in x -- known as type deconstructing

вернет 1, но

let [x] ++ [y, z] = [1, 2, 3] in x

вернет ошибку Variable not in scope x

Чтобы упростить процесс, представьте себе cons вот так

data List a = Cons a (List a) -- is equvalent with `data [a] = a:[a]`

https://en.wikibooks.org/wiki/Haskell/Other_data_structures

Кроме того, если вы хотите перевернуть массив с помощью cons.Вот пример, знания взяты из пролога

import Data.Function

reversex1 [] = []
reversex1 arr = reversex arr []

reversex [] arr = arr
reversex (x:xs) ys = reversex xs (x:ys)

main = do
    reversex1 [1..10] & print