Есть ли в Haskell завершающий фолд? - PullRequest
Новая
       65

Есть ли в Haskell завершающий фолд?

6 голосов
/ 01 мая 2020

Мне нужна какая-то свертка, которая может завершиться, если у меня уже есть нужные данные.

Например, мне нужно найти первые 3 числа, которые больше 5. Я решил использовать Either для завершения и мой код выглядит так: 

    terminatingFold :: ([b] -> a -> Either [b] [b]) -> [a] -> [b]
    terminatingFold f l = reverse $ either id id $ fold [] l
      where fold acc [] = Right acc
            fold acc (x:xs) = f acc x >>= flip fold xs

    first3NumsGreater5 acc x =
      if length acc >= 3
        then Left acc
        else Right (if x > 5 then (x : acc) else acc)

Существуют ли еще более умные / обобщенные c подходы?

Ответы [ 2 ]

6 голосов
/ 01 мая 2020

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

Раскрытие недооценивается для таких задач. Вместо того чтобы сосредоточиться на «потреблении» списка ввода, давайте подумаем о нем как о начальном элементе, из которого (в сочетании с некоторым внутренним аккумулятором) мы можем получить результат, элемент за элементом.

Давайте определим тип Seed который содержит обобщенный c аккумулятор в паре с пока еще не использованными частями ввода: 

{-# LANGUAGE NamedFieldPuns #-}
import Data.List (unfoldr)

data Seed acc input = Seed {acc :: acc, pending :: [input]}

Теперь давайте переформулируем first3NumsGreater5 как функцию, которая либо производит следующий элемент вывода из Seed сигналов о том, что больше нет элементов: 

type Counter = Int

first3NumsGreater5 :: Seed Counter Int -> Maybe (Int, Seed Counter Int)
first3NumsGreater5 (Seed {acc, pending})
  | acc >= 3 =
    Nothing
  | otherwise =
    case dropWhile (<= 5) pending of
      [] -> Nothing
      x : xs -> Just (x, Seed {acc = succ acc, pending = xs})

Теперь наша основная функция может быть записана в виде unfoldr: 

unfoldFromList ::
  (Seed acc input -> Maybe (output, Seed acc input)) ->
  acc ->
  [input] ->
  [output]
unfoldFromList next acc pending = unfoldr next (Seed {acc, pending})

Положить его на работу: 

main :: IO ()
main = print $ unfoldFromList first3NumsGreater5 0 [0, 6, 2, 7, 9, 10, 11]
-- [6,7,9]
2 голосов
/ 01 мая 2020

Обычно -качественный фолд с досрочным завершением равен foldr с функцией объединения, которая не является строгой во втором аргументе. Но его информационный поток направлен справа налево (если есть), а вы хотите, чтобы он был слева направо.

Возможное решение состоит в том, чтобы foldr функционировал как left fold, который затем можно сделать так, чтобы он остановился рано: 

foldlWhile :: Foldable t 
           => (a -> Bool) -> (r -> a -> r) -> r 
           -> t a -> r
foldlWhile t f a xs  =  foldr cons (\acc -> acc) xs a
  where
    cons x r acc | t x  =  r (f acc x) 
                 | otherwise  =  acc

Вам нужно настроить это на t, чтобы проверить acc вместо x, чтобы соответствовать вашим целям.

Эта функция foldlWhile из https://wiki.haskell.org/Foldl_as_foldr_alternative, немного переписана. foldl'Breaking оттуда может соответствовать требованиям немного лучше.

foldr с функцией ленивого редуктора может express corecursion прекрасно, как и unfoldr.

И ваш код уже ленивый: terminatingFold (\acc x -> Left acc) [1..] => []. Вот почему я не уверен, является ли этот ответ «более умным», как вы и просили.

edit: после комментария @danidiaz, чтобы сделать его ленивым, вы должны будете его кодировать, например, 

first3above5 :: (Foldable t, Ord a, Num a) 
             => t a -> [a]
first3above5 xs  =  foldr cons (const []) xs 0
   where
   cons x r i | x > 5  =  if i==2 then [x]
                                  else x : r (i+1)
              | otherwise  =  r i

Это может быть далее обобщается путем абстрагирования теста и подсчета.

Конечно, это просто переопределение take 3 . filter (> 5), но показывает, как это сделать в целом с foldr.

...