У Haskell есть сворачивание? - PullRequest
Новая
       28

У Haskell есть сворачивание?

8 голосов
/ 19 января 2012

Как можно строго сложить монаду?Data.Foldable имеет строгий foldl' и монадический foldlM, но не строгий foldlM'?Строгость как-то определяется самой монадой?Если так, как можно понять, что это такое?

Представьте, что я должен определить, является ли произведение огромного списка элементов кольца нулевым, но мое кольцо не является интегральной областью, то есть содержит ноль девизоров.В этом случае я должен рекурсивно подсчитывать foldl моего умножения *** по списку, но возвращать False в тот момент, когда продукт становится равным нулю, вместо ожидания полного продукта.

safelist :: [p] -> Bool
safelist [] = True
safelist (x:xs) = snd $ foldl' f (x,True) xs
   where  f (u,b) v = (w, b && w /= Zero)  where  w = u *** v

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

1 Ответ

9 голосов
/ 19 января 2012

Нет такой стандартной функции, но ее легко определить: 

foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
  z' <- f z x
  z' `seq` foldM' f z' xs

Это просто стандарт foldM, но с тем же значением seq, что и foldl' (по сравнениюдо foldl).Вероятно, он нигде не определен в качестве стандарта, поскольку вряд ли он будет настолько полезен: для большинства монад (>>=) является «строгим» в том смысле, что вам нужно использовать левую складку без переполнения стека;это полезно только в том случае, если ваши чрезмерные отклонения находятся в самих возвращаемых значениях, но полезное приложение foldM выполнит некоторое монадическое вычисление со значением из последнего шага, делая это маловероятным.достаточно прост, как есть;Я сомневаюсь, что foldM' сделает его более элегантным.

...