Корреспондент Haskell слишком строг? - PullRequest
Новая
       43

Корреспондент Haskell слишком строг?

5 голосов
/ 02 мая 2019

Я писал свой код с Control.Monad.Writer.Lazy, используя (,) [String] в качестве моей монады писателя.Но я обнаружил, что (>>=) и (>>) слишком строги с оператором моноида?Они вызывают бесконечный цикл с этим кодом, например: 

type Wrtr a = ([String], a)
writer (x, w) = (w, x)

main :: IO ()
main = do
    let one = writer ((), ["goodbye"])
    let w = foldr1 (>>) $ repeat one
    let (log, _) = w
    mapM_ putStrLn . take 5 $ log

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

data Writer w a = Writer w a
instance Functor (Writer w) where
    fmap f (Writer w x) = Writer w (f x)
instance Monoid w => Applicative (Writer w) where
    pure x = Writer mempty x
    (Writer w1 f) <*> (Writer w2 x) = Writer (w1 <> w2) (f x)
instance Monoid w => Monad (Writer w) where
    return = pure
    (Writer w1 x) >>= f =
        let (Writer w2 y) = f x
        in Writer (w1 <> w2) y
writer (x, w) = Writer w x

(Вы должны определить функтор и аппликативные экземпляры из-за ограничения моноида)

Если вы затем выполните код с той же самой функцией main, что и выше, он напечатает «до свидания» пять раз и завершится.

Итак, вопрос: почему кортежи такие строгие?Или если это не строгость, что это и почему это там?

Кстати, я использую ghc 8.6.4 и все остальное, что идет со стеком lts-13.19

Ответы [ 2 ]

5 голосов
/ 02 мая 2019

Это потому, что ваш Writer нарушает законы монады.Посмотрите на этот закон: 

-- forall (f :: a -> Writer m b) (x :: a).
return x >>= f = f x
-- basically f (id x) = f x, which we should agree is pretty important!

Но, увы, он не выполняется!let f = undefined!(или f = const undefined; они неразличимы, если вы не используете seq) 

  return x >>= undefined
= Writer mempty x >>= undefined
= let (Writer m y) = undefined
  in  Writer (mempty <> m) y
= Writer (mempty <> undefined) undefined

Тем не менее, по закону, 

  return x >>= undefined
= undefined x
= undefined

Это не эквивалентно, поэтому ваш ленивыйMonad экземпляр является незаконным (и да, я полагаю, так же, как и в mtl).Тем не менее, Быстрые и бесполезные рассуждения нравственно правильны , поэтому мы обычно просто принимаем это.Идея состоит в том, что ленивая Writer монада, как правило, следует законам, которые она должна соблюдать, до тех пор, пока вы сохраняете из нее бесконечные или нижние значения, но она ломается в этих крайних случаях.Напротив, строгое выполнение полностью законно, и поэтому оно находится в base.Однако, как вы обнаружили, когда ленивые Writer s нарушают закон, они делают это полезным способом, поэтому мы помещаем ленивую реализацию в mtl.

Вот демонстрационная версия этого поведения .Обратите внимание, что ленивая версия выдает Writer " на выходе до взрыва, в то время как строгая версия и спецификация, установленные законом, не делают этого.

4 голосов
/ 02 мая 2019

Hackage говорит 

instance Monoid a => Monad ((,) a) where
    (u, a) >>= k = case k a of (v, b) -> (u <> v, b)

, и это означает, что они строгие из-за case (в отличие от вашего let (Writer w2 y) = f x): 

foldr1 (>>) $ repeat one
= one >> foldr1 (>>) (repeat one)
= (["goodbye"], ()) >>= \_ -> foldr1 (>>) (repeat one)
= case ((\_ -> foldr1 (>>) (repeat one)) ()) of (v, b) -> (["goodbye"] <> v, b)
= case (foldr1 (>>) (repeat one)) of (v, b) -> (["goodbye"] <> v, b)

иэто фактически вынуждает вложенный (foldr1 (>>) ...), прежде чем вы сможете получить доступ к части ["goodbye"] <> v.

Это происходит потому, что сопоставление с шаблоном case является принудительным, а шаблоны let являются ленивыми.Ваш действующий код записывает вышеизложенное как 

= let (v, b) = foldr1 (>>) (repeat one) in (["goodbye"] <> v, b)

, и все нормально и лениво.

...