Обратный список в haskell

Я пытаюсь изменить список.

Ниже приведен мой код:

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

В результате я получаю список в том же порядке. У меня даже есть решение, как изменить список, но я пытаюсь понять, что я сделал неправильно здесь? Я очень новичок в haskell, поэтому думаю, что я должен сосредоточиться на понимании больше, чем я могу решить больше проблем с легкостью. Я знаю, что есть много решений для этой проблемы, но мне нужна дополнительная помощь в понимании esp, что я сделал не так здесь в этом коде.

Ответ 1

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

В первом вызове x будет 1, а xs будет [2, 3]. Затем вы создаете новый список, состоящий из x (так 1) в начале, а затем reverseList [2, 3].

Ответ 2

Существует несколько способов решения этой проблемы в Haskell. Наивный подход заключался бы в использовании функции конкатенации ++:

reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

Однако для больших списков это будет очень медленным, так как списки Haskell являются действительно связанными списками, поэтому, чтобы добавить элемент, вам нужно пройти весь список. Альтернативой было бы идти в ногу со списком, который вы строите в вспомогательной функции:

reverseList = go []
    where
        go acc [] = acc
        go acc (x:xs) = go (x:acc) xs

Однако это действительно просто шаблон fold:

reverseList = foldl (\acc x -> x : acc) []

Но \acc x -> x : acc просто flip (:), поэтому это можно записать как

reverseList = foldl (flip (:)) []

Однако самым простым способом, вероятно, было бы просто использовать функцию reverse в Prelude.

Я хотел бы указать, что ваш тип reverseList :: [Int] -> [Int] может быть обобщен на :: [a] -> [a], вы не делаете ничего особенного с элементами списка, вы просто строите с ними новый список.

Ответ 3

Есть несколько способов решить эту проблему в Haskell. Вот решение с минусами и последними /init:

reverseList  [] = []
reverseList  xs = last xs : reverseList (init xs)

Или со сложением:

reverseList xs = foldl (\x y -> y:x) [] xs

Ответ 4

В основном наивный алгоритм, который использует добавление

revList [] = []
revList (x:xs) = revList xs ++ [x]

неэффективно, так как добавление является операцией O(n) где n - длина первого (левого) параметра оператора ++. Таким образом, revList выше функция revList оказывается O (n (n-1)/2) ~ O (n ^ 2).

Так что для таких сложных задач есть тип данных Список различий.

Список различий - это просто список, выраженный как функция. Я имею в виду, что список типа [1,2,3] в выражении типа DList будет иметь вид \xs → [1,2,3] ++ xs или короче ([1,2,3] ++)

type DList a = [a] -> [a]

toDList :: [a] -> DList a
toDList xs  = (xs ++ )

fromDList :: DList a -> [a]
fromDList f = f []

Это круто, потому что DList - это функции, мы можем добавить их с помощью оператора композиции (.) И получить новый DList. Другими словами toDList (xs ++ ys) == (toDList xs). (toDList ys) toDList (xs ++ ys) == (toDList xs). (toDList ys).

Так как это полезно? Используя композиции вложенных функций, мы можем перевернуть наш список аналогично функции revList но это будет стоить нам намного дешевле. Только O (n), поскольку каждая композиция функций является O (1).

revList' :: [a] -> DList a
revList' []     = toDList []
revList' (x:xs) = revList' xs . toDList [x]

Теперь, когда у нас есть обратный [a] в DList a тип, все, что нам нужно применить из fromDList

fastReverse :: [a] -> [a]
fastReverse = fromDList . revList'