Неожиданный результат при изменении списка

Question

Мне нужно некоторое объяснение неожиданного результата кода ниже, по-видимому, из-за какой-то ошибки.

reverse' :: [b] -> [b]
reverse' [] = []
reverse' [x] = [x]
reverse'(x:xs) = last (x:xs) : reverse' xs

*Main> reverse' [0,8,2,5,6,1,20,99,91,1]
[1,1,1,1,1,1,1,1,1,1]

Это из-за какой-то ошибки?

Answer 1

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

reverse' (0:[8,2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : (reverse' (8:[2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : 1 : (reverse' (2:[5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
...

Вы можете видеть, куда это идет.Проблема проста;вы просто переворачиваете неправильную часть списка в рекурсивном шаге.Вместо того, чтобы перевернуть хвост, как вы делаете сейчас, вы хотите перевернуть все, кроме последнего элемента.Таким образом, вы можете изменить его на что-то вроде этого:

reverse' :: [b] -> [b]
reverse' [] = []
reverse' [x] = [x]
reverse' xs = last xs : reverse' (init xs)

, что возвращает то, что вы ожидаете: reverse' [1,91,99,20,1,6,5,2,8,0] = [0,8,2,5,6,1,20,99,91,1]

Answer 2

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

rev xs = rev' xs [] where
  rev' [] acc = acc
  rev' (x:xs) acc = rev' xs (x:acc) 

Итак, выиметь подфункцию с дополнительным аргументом («аккумулятор»), который собирает то, что у вас уже есть.Очевидно, что в базовом случае вам нужно вернуть этот результат, потому что вы сделали.В данном случае рекурсивный случай очень прост: это все равно, что иметь стопку пластин, которую вы берете одну за другой сверху, и строите новую стопку, добавляя одну за другой сверху.Этот результирующий стек переворачивается, как нам и нужно.

Обратите внимание, что для некоторых других применений этого метода вы не хотите этого возврата, который можно исправить, вставив reverse в базовый вариант.

Answer 3

Минимальное исправление к вашему исходному коду возможно

-- reverse'(x:xs) = last (x:xs) : reverse' xs
reverse' (x:xs) = reverse' xs ++ [x]

т.е. Вы комбинировали части своего списка в неправильном порядке.

Это, конечно, еще квадратичный алгоритм. Вы получаете итерационную версию, сначала наблюдая за

reverse' (a:b:c:d:xs) = (((reverse' xs ++ [d]) ++ [c]) ++ [b]) ++ [a]

, а затем перегруппировка и сохранение сформированных таким образом промежуточных результатов в отдельном аргументе аккумулятор , как было указано в предыдущем ответе:

rev (x:xs) acc = rev xs (x:acc)

Найдя свою рабочую лошадку, вы настраиваете ее с соответствующим интерфейсом,

reverse' xs = rev xs []

(плюс несколько крайних случаев).

Answer 4

Играя с Data.Monoid, я нашел следующую альтернативу, слегка рубиново-золотого цвета:

import Data.Foldable
import Data.Monoid

reverse = getDual . foldMap (Dual . (:[])) 

Answer 5

reverse2 :: [a] -> [a]
reverse2 [] = []
reverse2 [x] = [x]
reverse2 x = (last x) : (reverse2 (init x))