#haskell
#haskell
Вопрос:
Я пытаюсь написать функцию в haskell, которая рекурсивно меняет списки. Я написал вспомогательную функцию, которая принимает исходный список и пустой список, а затем переносит элементы из первого в другой в шаблоне LIFO.
Вот что у меня есть:
myreverse :: [a] -> [a]
myreverse list = myflip list []
myflip :: [a] -> [a] -> [a]
myflip list1 newList
| null list1 = newList
| otherwise = myflip (tail list1) ((head list1) : newList)
Я знаю, что есть встроенная функция, которая делает это за меня, но требование состоит в том, чтобы я использовал только head, tail, elem и null (также без сопоставления с шаблоном). Итак, мой вопрос: есть ли лучшее решение, в котором у меня есть только одна функция, myreverse , которая использует только один список? (Конечно, это соответствует вышеуказанным требованиям)
Спасибо!
Комментарии:
1. Да. И то, что у меня есть, даст мне полную оценку. Я просто хочу знать, есть ли более элегантный способ сделать это, учитывая вышеуказанные требования.
2. Вы также используете
(:), но его нет в списке разрешенных функций 😉3. Да, есть много способов сделать это, но ограничения затрудняют создание хорошей функции. 🙂
4. Это неразрешимо, потому что ни один из tail , elem, head и null не приводит к списку того же типа и, по крайней мере, такой же длины, как один из аргументов. Но результатом должен быть список того же типа и той же длины, что и аргумент. Q.E.D.
5. @sth
(:)— это конструктор данных, а не конструктор типов. Его тип равен(:) :: a -> [a] -> [a], поэтому он логически является функцией из-за его типа, содержащего хотя бы одну стрелку. Страница Википедии, посвященная алгебраическим типам данных , описывает конструктор данных как нечто похожее на функцию, но затем в следующем предложении говорится, что это логически функция. Конечно, если мы хотим иметь хоть какую-то надежду на решение проблемы, мы должны разрешить ее использование!
Ответ №1:
Вы можете попробовать изменить список, используя foldl примерно так:
reverse' :: [a] -> [a]
reverse' = foldl (acc x -> x : acc) []
Комментарии:
1. Или немного более причудливый
foldl (flip (:)) []2. Спасибо, но это не соответствует требованиям. :
3. @Sadiq
reverse' sNew = foldl (flip (:)) sNewпринимает 2 списка и возвращает перевернутую строку. Имейте в виду, что Haskell всегда возвращает новое значение. Я не знаю, зачем вам когда-либо нужно было передавать значение для хранения вашего нового результата. Неизменяемые языки не подвержены тем же опасностям, что и императивные.
Ответ №2:
Итак, для всех, кому может быть интересно, это то, что я в итоге написал:
myreverse :: [a] -> [a]
myreverse list = myflip list []
where myflip list newList = if null list then newList
else myflip (tail list) ((head list):newList)
Спасибо всем за ваши комментарии и предложения.
Ответ №3:
сохраните это в файле reverse.hs
reverseString :: [Char] -> [Char]
reverseString [] = []
reverseString (x:xs) = reverseString xs [x]
затем запустите
reverseString «abc»
cba
Ответ №4:
Помимо настроек, необходимых для удовлетворения ваших дополнительных требований, ваша функция эквивалентна способу reverse реализации в GHC. Поэтому я бы предположил, что ваша функция довольно хороша такой, какая она есть.
Ответ №5:
Эта функция удовлетворяет вашим требованиям, но ужасно неэффективна:
rev xs = if null xs then xs else rev (tail xs) [head xs]
Ваше решение совсем не плохое. После использования сопоставления с образцом и создания myFlip локальной функции это не будет выглядеть уродливо. И техника использования локальной функции с аккумулятором очень распространена (хотя и не в таких простых случаях).
Комментарии:
1. Я думал об этом, но, к сожалению, оператор не соответствует требованиям. 🙁 Хотя спасибо за помощь!
2. @Uqi: тогда напишите свой собственный
:app xs ys = if null xs then ys else head xs : app (tail xs) ys