Развернуть, вернув последнее состояние аккумулятора

Question

unfold Функция в Haskell очень удобна для создания списков. Его определение таково:

unfold :: (b -> Maybe (a, b)) -> b -> [a]

Но я бы хотел получить последнее значение используемого аккумулятора. Возможная реализация:

unfoldRest :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest fct ini = go fct ini []
  where
    go f s acc =
      case f s of
        Nothing -> (acc, s)
        Just (a, b) -> go f b (acc ++ [a])

Но мне было интересно, если бы не было способа сделать это с существующими функциями. В конце концов это:

countDown 0 = Nothing
countDown n = Just (n, n-1)
unfoldRest countDown 10

вернусь:

([10,9,8,7,6,5,4,3,2,1],0)

Поскольку итерация остановилась, когда значение аккумулятора достигло 0,

Answer 1

import Data.List

unfoldr' :: (b -> Maybe (a, b)) -> b -> [(a, b)]
unfoldr' f = unfoldr (fmap (\(a, b) -> ((a, b), b)) . f)

даст вам все состояния аккумулятора. Затем вы можете посмотреть, что хотите, включая последнее.

Answer 2

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

unfoldRest' :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest' f s = case f s of
    Nothing -> ([], s)
    Just (a, b) -> (\ ~(xs, y) -> (a : xs, y)) $ unfoldRest' f b

Ленивый образец совпадения (~(xs, y) в лямбде) важно; это позволяет вам смотреть на первые элементы списка без необходимости вычислять конечное состояние и, следовательно, делать что-то полезное с бесконечными списками (в любом случае решение Тома Эллиса лучше для бесконечных списков, как вы можете видеть не только сгенерированные значения, но и состояние после любого произвольного сегмента). Как указывает Уилл Несс, вы можете найти правую часть Just случай более естественный для записи с использованием let обязательный, как в let (xs, y) = unfoldRest' f b in (a : xs, y),

Поскольку вы пометили вопрос "pointfree", стоит упомянуть, что вы можете значительно уменьшить количество баллов, используя maybe и Control.Arrow комбинаторы:

import Control.Arrow ((***), first, app)

unfoldRest'' f s =
    maybe ([], s) (app . (first . (:) *** unfoldRest'' f)) $ f s

Хотите ли вы пойти так далеко - дело вкуса. Проблема лени решается правильно, так как реализация (***) для функций используется ленивое сопоставление с образцом.

Answer 3

Я сталкивался с этой проблемой раньше - один из способов решить ее - использовать монаду State .

Проще говоря, они имеют дело с функциями на форме. Интуитивно, s— тип состояния, которое может измениться во время вычисления.

Первое, что нужно отметить, это то, что s -> Maybe (d, s)не имеет формы: первое представляет собой кортеж вещей, а второе — Maybe, нам нужна функция типа s -> (Maybe d, s), если функция возвращает None, измененная функция вернет предыдущее состояние. Одна из возможных реализаций этого адаптера:

      keepFailure :: (s -> Maybe (d, s)) -> (s -> (Maybe d, s))
keepFailure f s = maybe (Nothing, s) (first Just) (f s)

Запомни import Data.Bifunctorиз-за firstфункция Есть функция, которая преобразует из s -> (d, s)к State s dназывается state, и преобразовать его обратно. Теперь мы реализуем функцию, которая будет пытаться исчерпать состояние всех возможных значений:

      stateUnfoldr :: State s (Maybe d) -> State s [d]
stateUnfoldr f = do
  mx <- f
  case mx of
    Just x -> do
      xs <- stateUnfoldr f
      return $ x:xs
    Nothing -> return []

Проще говоря, mx <- fработает как «применить к входу, обновить состояние, получить присвоить возвращаемое значение mx«Тогда мы можем собрать все вместе:

      fStateUnfoldr :: (s -> Maybe (d, s)) -> (s -> ([d], s))
fStateUnfoldr f = runState $ stateUnfoldr $ state . keepFailure $ f

Запомни import Control.Monad.State

state . keepFailureадаптируется fв State s (Maybe d)Монада, тогда stateUnfoldrразворачивается в State s [d], затем превращает его обратно в функцию.

Мы также можем использовать execStateили же evalStateвместо runStateесли вы хотите только состояние или просто список.