Различия между Haskell (:) и (++)

Ответ 1

Оператор : известен как оператор "cons" и используется для добавления элемента заголовка в список. Итак, [] - это список, а 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] действительно.

Ответ 2

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

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

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

a -> [a] -> [a]

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

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

Ответ 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 (:)!!!

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

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

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

Здесь есть одна вещь.

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

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

С уважением,

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

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

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

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

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

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

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

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

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

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

Ответ 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. Вот пример, знание взято из Prolog

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