Разделение списка в подсписках в Haskell

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

Мое базовое решение:

partSameElems :: [a] -> ([a],[a])
partSameElems [] = ([],[])
partSameElems (x:xs) = fstList (x:xs) scdList (x:xs) where fstList (x:y:xs) = if x == y then x:y:fstList xs {- I need to do Nothing in else section? -} scdList (x:xs) = x:scdList xs

Например: [3,3,3,3,2,1,3,3,6,3] → ([3,3,3,3], [2,1,3,3,6,3])

Теперь я могу предложить свою версию решения:

partSameElems :: Eq a => [a] -> ([a],[a])
partSameElems [] = ([],[])
partSameElems (x:xs) = (fstList (x:xs), scdList (x:xs))
where fstList [] _ = [] fstList (x:xs) el = if x == el then x:fstList xs el else [] scdList [] _ = [] scdList (x:xs) el = if x /= el then (x:xs) else scdList xs el
3 ответа

Это проще, если вы не пытаетесь сделать это за два прохода.

parSameElems [] = ([], [])
parSameElems lst = (reverse revxs, ys) where (revxs, ys) = accum [] lst accum xs [y] = ((y:xs), []) accum xs (y1:y2:ys) | y1 == y2 = accum (y1:xs) (y2:ys) | otherwise = ((y1:xs), (y2:ys))

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

Примечание. Я на самом деле не запускаю это. Убедитесь, что вы попытаетесь отладить его.

Кроме того, не пишите подпись типа самостоятельно. Пусть ghci скажет вам. В первой попытке вы ошибались.


Я предполагаю, что "не прибегая к функции Прелюдии" означает, что он образован. Вероятно, он нацелен на работу над рекурсией, учитывая его манипулирование данными List. Поэтому давайте подчеркнуть это

Рекурсивные алгоритмы проще выразить, когда типы ввода и вывода идентичны. Скорее скажем, что вместо списка [3,3,3,3,2,1,3,3,6,3] ваши входные данные состоят из

  • передний список, но на этом этапе он пуст
  • остальная часть на данном этапе равна входным данным [3,3,3,2,1,3,3,6,3]
  • рекурсивный вход затем ([],[3,3,3,2,1,3,3,6,3])

Тип центральной функции будет ([a],[a]) → ([a],[a])

Теперь каждый шаг рекурсии берет передний элемент остатка и либо помещается, если находится в переднем списке, либо останавливает рекурсию (вы достигли конечного состояния и можете вернуть результат)

module SimpleRecursion where
moveInFront :: (Eq a) => ([a],[a]) -> ([a],[a])
moveInFront (xs , [] ) = ( xs , [])
moveInFront ([] , y:ys ) = moveInFront ( y:[] , ys)
moveInFront (x:xs , y:ys ) = if x == y then moveInFront ( y:x:xs , ys) else (x:xs, y:ys)
partSameElems :: (Eq a) => [a] -> ([a],[a])
partSameElems a = moveInFront ([],a)

То, что мы имеем здесь, представляет собой классическую рекуррентную схему, с условием - stop (x/= y) - рекурсивной оговоркой - охватом тривиальных случаев

Примечания: - запись y:x:xs фактически отменяет передний список, но поскольку все значения равны, результат в порядке. Пожалуйста, не делайте такого трюка в коде реальной программы, он вернется, чтобы укусить вас в конце концов - функция работает только над списками Equatable data (Eq a) => потому что условие рекурсии/остановки является тестом равенства ==


Другая реализация может быть

partition [] = ([],[])
partition xa@(x:xs) = (f,s) where f = takeWhile (==x) xa s = drop (length f) xa

должно быть ясно, что он делает.

> partition [3,3,3,3,2,1,3,3,6,3]
([3,3,3,3],[2,1,3,3,6,3])

licensed under cc by-sa 3.0 with attribution.