Ошибка возврата списка Haskell

Question

Я пишу программу разворота списка для haskell.

У меня есть идея для разворота списка и это приводит к следующему коду:

myreverse list1 
| list1 == [] = list1 
| otherwise  = (myreverse(tail list1)):(head list1) 

К сожалению, приведенные выше результаты кода в следующей ошибки:

Occurs check: cannot construct the infinite type: a = [[a]] 
Expected type: [[a]] 
Inferred type: a 
In the second argument of '(:)', namely '(head list1)' 
In the expression: (myreverse(tail list1)):(head list1) 

PS: Я получить такую ​​же ошибку, когда я запустил ее в фрагменте, который я написал, назвал mylast, закодированным ниже:

mylast list 
| list == []  = [] 
| otherwise  = mylast_helper(head list1)(tail list1) 

mylast_helper item list2 
| list2 == []  = item 
| otherwise  = mylast_helper(head list2)(tail list2) 

Ошибка в противном случае рекурсивного помощника.

EDIT: Спасибо за все входные данные, я, наверное, забыл упомянуть, что ограничения вопроса запрещают использование оператора ++. Я буду держать это в виду для будущих вопросов, которые я создаю.

Приветствия, -Zigu

Answer 1

Типом минусах (:) является a -> [a] -> [a] - другими словами, вы даете ему элемент, а затем список и помещает элемент в начале списка. В последней строке вы сначала делаете обратный список, а затем - элемент. Чтобы исправить это, изменить : к списку Concat оператора ++:

myreverse list1 
    | list1 == [] = list1 
    | otherwise = (myreverse (tail list1)) ++ [head list1] 

(Чтобы попытаться перевести эту ошибку, она говорит: «Хорошо, первый аргумент : ты дал мне список, поэтому второй аргумент должен быть списком элементов того же типа, поэтому список списков ... НО ... вы дали мне аргумент, который является типом элемента списка, поэтому мне нужен какой-то тип это то же самое, что список списков такого типа, который я не могу сделать. Bang! »)

Answer 2

Прежде всего, попробуйте добавить подпись к каждой из ваших функций; это поможет компилятору узнать, что вы пытаетесь сделать, и дать более качественные сообщения об ошибках ранее. Подпись будет выглядеть так: mylast :: [a] -> a. Затем, вместо того, чтобы использовать защитные (|), определить свою функцию через ряд уравнений, используя поиск по шаблону:

mylast :: [a] -> a 
mylast (x:[]) = x 
mylast (_:t) = mylast t 

В GHCi, вы можете посмотреть на тип что-то с помощью :tтермин. Это лучший общий совет, который я могу дать ... внимательно посмотрите на типы и убедитесь, что они имеют смысл, как вы их используете.

Answer 3

Вы используете функцию

(:) :: a -> [a] -> [a] 

с плохо напечатанный аргументами:

myReverse (tail list1) :: [a] 
head list1 :: a 

В вашей функции, перечень песни1 должны иметь тип . Следовательно, второй аргумент, head list1, должен иметь тип [a]. GHC предупреждает вас о том, что он не может создать тип, который вы указали для него.Глава списка структурно меньше хвоста списка, но вы говорите, что глава списка имеет тип [a], но хвост списка имеет тип a.

Если вы смотрите внимательно на ваших типов, однако, вы заметите, что вы можете добавить глава песни1 на рекурсивный вызов myreverse использованием (++):

myReverse xs = case (null xs) of 
       True -> xs 
       False -> myReverse (tail xs) ++ [head xs] 

Здесь

[head xs] :: [a] 
myReverse (tail xs) :: [a] 

который выравнивает с типом Append:

(++) :: [a] -> [a] -> [a]

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

reverse xs = foldr (\x xs -> xs ++ [x]) [] xs 

Answer 4

Законченной работать над этим вопросом все больше и отвечать сам. Спасибо большое за обратную связь. Он толкнул меня вперед в правильном направлении.

myreverse list1 
| list1 == [] = list1 
| otherwise = myreverse_h(list1)([]) 

myreverse_h list1 list2 
| list1 == [] = list2 
| otherwise = myreverse_h(tail list1)((head list1):list2) 

Любые комментарии по улучшению кода, хотя? Я не думаю, что его как efficien t, поскольку это могло бы быть ...