Есть ли нерекурсивный способ написать эту функцию «paginate»?

Question

Следующая функция не в стандартных библиотеках Haskell, так что я написал:

paginate _ [] = [] 
paginate n xs = let (h, t) = splitAt n xs in h : paginate n t 

Тогда я хотел бы переписать его без явной рекурсии пока еще легко понять.

Я попробовал версию fix, которая не уступает весьма удовлетворительные результаты:

paginate = fix go 
    where 
    go _ _ [] = [] 
    go v n xs = let (h, t) = splitAt n xs in h : v n t 

Существуют ли простые решения, которые используют функции Prelude?

Answer 1

Когда я вижу такую ​​проблему, мне нравится думать о «форме» функции, которую вы хотите. В этом случае вы начинаете со списка и составляете список списков. Это частный случай, начинающийся с одного значения и создающий список, который соответствует разворачивается. Итак, если вы не возражаете импортировать Data.List, вы можете аккуратно написать свою функцию, используя unfoldr.

Давайте посмотрим, как это сделать шаг за шагом. Во-первых, как и выше, вы просто должны знать о unfoldr и видеть, что он может применяться. Здесь немного опыта (например, чтение ответов, как этот :)) приходит в

Далее мы посмотрим на тип unfoldr:.

Prelude Data.List> :t unfoldr 
unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

Идея заключается в том, что мы начинаем с одно значение «ядро» (b) и повторно нажимайте функцию шага (b -> Maybe (a, b)), пока мы не нажмем Nothing. Наша стартовая ценность - это список, который мы хотим разделить на куски, поэтому нам больше не нужно заниматься обработкой. Это означает, что последний шаг, который мы выполняем, - это реализация функции шага.

Поскольку мы начинаем со списка значений, мы можем заменить b на [n]; более того, поскольку мы хотим составить список списков в самом конце, мы можем заменить [a] на [[n]] и, следовательно, a с [n]. Это дает нам окончательный вид, мы должны реализовать для ступенчатой ​​функции:

[n] -> Maybe ([n], [n]) 

Эй, что очень похож на тип splitAt!

splitAt :: Int -> a -> ([a], [a]) 

На самом деле, мы можем просто обернуть результат splitAt в Just и отвечают соответствующим требованиям наших типов. Но это оставляет очень важную роль: финальный Nothing, который сообщает unfoldr, чтобы остановиться! Поэтому наша вспомогательная функция нуждается в дополнительном базовом футляре для [], чтобы вернуть правильный результат.

Собирает все вместе дает нам окончательную функцию:

import Data.List (unfoldr) 

paginate n = unfoldr go 
    where go [] = Nothing -- base case 
     go ls = Just (splitAt n ls) 

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

Если вы не возражаете, позволяя расширение (LambdaCase), вы можете переписать это в несколько аккуратным способом, избегая имен go:

paginate n = unfoldr $ \case 
    [] -> Nothing 
    ls -> Just (splitAt n ls) 

Answer 2

FYI, вытекающий из ответа Тихона Jelvis', я в конце концов закончилась с

boolMaybe p f x = if p x then Just (f x) else Nothing 
groupWith  = unfoldr . boolMaybe null 
paginate  = groupWith . splitAt 

, который слишком запутан для меня. Вернемся к рекурсивной версии.

Answer 3

Вот немного измененная версия кода Тихона Jelvis':

import Data.Maybe 
import Data.List 
import Control.Applicative 

paginate n = unfoldr $ \xs -> listToMaybe xs *> Just (splitAt n xs) 

Или в pointfree:

paginate n = unfoldr $ (*>) <$> listToMaybe <*> Just . splitAt n 

Answer 4

там всегда было:

import Data.List 

chunks n = takeWhile (not . null) . unfoldr (Just . splitAt n) 

но новый чемпион, для меня, является

import Data.Maybe     -- additional imports 
import Control.Applicative 

chunks n = unfoldr $ (<$) . splitAt n <*> listToMaybe 
       -- \xs -> splitAt n xs <$ listToMaybe xs 

(настройка чуть-чуть кода from this comment by @ user3237465).

Биты, используемые здесь:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 
(f <*> g) x = f x (g x)    -- S combinator 
x <$ c = fmap (const x) c   -- "mapped into" 
listToMaybe xs = head (map Just xs ++ [Nothing]) 

Другой подобный способ написать это

import Control.Monad     -- an additional import 

chunks n = unfoldr $ listToMaybe . join ((<$) . splitAt n) 
       -- \xs -> listToMaybe (splitAt n xs <$ xs) 

с использованием монадическая join для функций,

join f x = f x x      -- W combinator