Превратите список в список списков с помощью fold в haskell

У меня есть этот код:

fromList :: Int -> [Int] -> [[Int]]
fromList y = takeWhile (not.null) . map (take y) . iterate (drop y)

Пример того, что это делает: -> fromList 4 [1..19]

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19]]

Как я могу сделать этот код с помощью сгиба?


list chunks fold haskell sublist
person John Smith    schedule 04.11.2020    source источник
comment
Подсказка: используйте [[a]] как тип аккумулятора.   -  person Willem Van Onsem    schedule 05.11.2020
comment
Почему? Это лучше?   -  person John Smith    schedule 05.11.2020
comment
Это действительно работа для unfoldr; почему вы хотите использовать foldr?   -  person chepner    schedule 05.11.2020
comment
В то время как (я думаю) один из них может выполнять работу другого, складки предназначены для вещей с общей формой [a] -> a, а разворачиваются для a -> [a]. (Сам a может быть типом списка, учитывая перекрытие между двумя функциями.)   -  person chepner    schedule 05.11.2020
comment
Рассмотрим fromList n = unfoldr (\x -> if null x then Nothing else Just (take n x, drop n x)).   -  person chepner    schedule 05.11.2020

Ответы (2)


arrow_upward
3
arrow_downward

Вот довольно элегантное решение с использованием foldr:

fromList :: Int -> [a] -> [[a]]
fromList n = foldr (\v a ->
    case a of
        (x:xs) -> if length x < n then (v:x):xs else [v]:a
        _ -> [[v]]
    ) []

По сути, аккумулятор является конечным значением, и для каждого значения в списке он проверяет, есть ли еще место, чтобы поместить его в существующий фрагмент, и если его нет, он помещает его в новый фрагмент. К сожалению, из-за использования foldr дополнительные элементы помещаются слева, а не справа. Это можно исправить, используя немного более медленный (и, возможно, немного более уродливый) подход с foldl (или foldl'):

fromList :: Int -> [a] -> [[a]]
fromList _ [] = []
fromList n (x:xs) = reverse $ foldl (\a@(y:ys) v ->
    if length y < n
        then (y ++ [v]):ys
        else [v]:a
    ) [[x]] xs
person Aplet123    schedule 05.11.2020
comment
Я дал 2 возможных решения, первое из которых помещает дополнительный фрагмент слева, что приводит к [[1], [2, 3, 4], [5, 6, 7], [8, 9, 10]], а второе приводит к [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]], как я указал в своем ответе. - person Aplet123; 05.11.2020
comment
a@ означает, что a становится псевдонимом для y:ys. Вы можете просто использовать y:ys вместо a и избавиться от a@, если хотите. - person Aplet123; 05.11.2020

arrow_upward
2
arrow_downward

Вот один из способов.

foo :: Int -> [t] -> [[t]]
foo k xs | k > 0  =  foldr cons [] .
          zip xs . cycle $ (False <$ [2..k]) ++ [True]
  where
  cons (a,True)   ys  =  [a] : ys
  cons (a,False)  ys  =  (a:x) : zs
                         where
                         (x,zs) | null ys   = ([], [])
                                | otherwise = (head ys, tail ys)

-- > foo 3 [1..10]
-- => [[1,2,3],[4,5,6],[7,8,9],[10]]

-- > take 4 . foo 3 $ [1..]
-- => [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

-- > take 3 . map (take 2) . foo 3 $ [1..8] ++ undefined
-- => [[1,2],[4,5],[7,8]]

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

(edit: сделал это еще ленивее, чтобы последний пример работал, основываясь на идее Дэниел Фишер)

person Will Ness    schedule 05.11.2020