Я пытаюсь изменить список.
Ниже приведен мой код:
reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = x:reverseList xs
В результате я получаю список в том же порядке. У меня даже есть решение, как изменить список, но я пытаюсь понять, что я сделал неправильно здесь? Я очень новичок в haskell, поэтому думаю, что я должен сосредоточиться на понимании больше, чем я могу решить больше проблем с легкостью. Я знаю, что есть много решений для этой проблемы, но мне нужна дополнительная помощь в понимании esp, что я сделал не так здесь в этом коде.
Вы разделяете список на голову и хвост, но затем собираете список в том же порядке. Возьмите список [1, 2, 3] например:
В первом вызове x будет 1, а xs будет [2, 3]. Затем вы создаете новый список, состоящий из x (так 1) в начале, а затем reverseList [2, 3].
Существует несколько способов решения этой проблемы в 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], вы не делаете ничего особенного с элементами списка, вы просто строите с ними новый список.
Есть несколько способов решить эту проблему в Haskell. Вот решение с минусами и последними /init:
reverseList [] = []
reverseList xs = last xs : reverseList (init xs)
Или со сложением:
reverseList xs = foldl (\x y -> y:x) [] xs
В основном наивный алгоритм, который использует добавление
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'