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

Question

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

Ниже мой код:

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

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

Answer 1

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

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

Answer 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 functi в Прелюдии.

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