Haskell - Рекурсия по списку списков?

Кажется, я не могу понять, как делать рекурсию по списку списков в Haskell. Вот моя проблема:

type Symbol = String
type Sentence = [[Symbol]]

getSymbols :: [Sentence] -> [Symbol]
getSymbols [[]] = []
getSymbols ((sym:stmt):(stmts))
    | stmt == [] = getSymbols stmts
    | sym `elem` stmt = getSymbols ((stmt):(stmts))
    | otherwise = sym : getSymbols ((stmt):(stmts))

Я пытаюсь вернуть список всех символов, найденных в данном предложении, без дубликатов, например.

getSymbols [["A","B","C"],["D","A"],["E","B","C"]]

вернется:

["A","B","C","D","E"] --order does not matter--

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


recursion haskell
person willrobertshaw    schedule 25.02.2016    source источник
comment
Вы могли бы попытаться разложить проблему на более простые подзадачи? Например. сначала создайте большой список со всем, что есть в нем, а затем удалите дубликаты. Тогда ответом на ваш вопрос будет составление этих более простых функций.   -  person gallais    schedule 26.02.2016
comment
@gallais Потребуется ли мне для этого написать больше функций, или это все еще можно сделать в одной функции? Потому что я хочу решить проблему с помощью одной функции   -  person willrobertshaw    schedule 26.02.2016
comment
@willrobertshaw, я не думаю, что это хорошая идея. В основе функционального программирования лежит создание функций. Чем раньше вы привыкнете писать небольшие составные функции, тем лучше. Подумайте, что может быть более универсальным из маленьких кубиков Лего или игрушечной машинки?   -  person epsilonhalbe    schedule 26.02.2016

Ответы (3)


arrow_upward
1
arrow_downward

Попробуй это:

import Data.List
nub . concat $ [["A","B","C"],["D","A"],["E","B","C"]]
person Ivan David    schedule 25.02.2016
comment
Не могли бы вы добавить какое-то объяснение, очевидно, OP интересуется не результатом, а тем, как и почему - person epsilonhalbe; 26.02.2016

arrow_upward
1
arrow_downward

Попробуй это:

getSymbols          []  = []
getSymbols (   [] :xss) = getSymbols xss
getSymbols ((x:xs):xss)
    | x `elem` (getSymbols (xs:xss)) =      getSymbols (xs:xss)
    | otherwise                      = x : (getSymbols (xs:xss))
person PyRulez    schedule 26.02.2016
comment
Привет, я пробовал это, но у меня появляется ошибка типа в последней строке. Не удалось сопоставить тип "[Char]" с "Char" Ожидаемый тип: Символ Фактический тип: [Символ] В первом аргументе '(:)', а именно 'sym' В выражении: sym: (getSymbols (stmt: stmts)) Любая помощь? - person willrobertshaw; 01.03.2016

arrow_upward
0
arrow_downward

@gallais Потребуется ли мне для этого написать больше функций, или это все еще можно сделать в одной функции? Потому что я хочу решить проблему с помощью одной функции

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

Итак, начнем со следующего списка:

[["A","B","C"],["D","A"],["E","B","C"]]

И мы хотим найти список, содержащий все те же строки, без других и без дубликатов. Что, если мы сгладим список с помощью concat :: [[a]] -> [a]?

["A","B","C","D","A","E","B","C"]

Очевидно, что при той же постановке проблемы мы придем к одному и тому же ответу. Все, что важно, - это то, какие струны присутствуют; остальная часть структуры не имеет значения.

С этого момента нам просто нужно удалить дубликаты в списке. Есть несколько способов сделать это. Неэффективный - nub :: Eq a => [a] -> [a]. Более эффективный метод - Set.toList . Set.fromList :: Ord a => [a] -> [a] с import qualified Data.Set as Set. Что бы мы ни выбрали, наше решение выглядит так:

nub . concat

Бонус: разработайте метод удаления дубликатов, который использует sort :: Ord a => [a] -> [a] из Data.List.

person erisco    schedule 10.05.2017