为什么 Alternative 的 some 和 many 是 haskell 中的无限递归函数
why Alternative's some and many are infinite recursive functions in haskell
我正在查看 haskell 中的 Alternative
类型类,当我发布这个
时我正在 ghci 中使用它
some (Just 2)
挂了,我看了Alternative的源码,Alternative的很多默认定义是这样的:
some :: f a -> f [a]
some v = some_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
-- | Zero or more.
many :: f a -> f [a]
many v = many_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
很明显,some_v
和many_v
是间接无限递归的,它们不是根据empty
和<|>
定义的。
如果它们必须由实例定义,那么它们不应该有默认定义,对吧?由于 Maybe
没有定义它们,所以我上面的陈述被绞死了,这对我来说很奇怪,因为文档中没有提到它。
那么为什么要这样定义它们呢?有什么我想念的吗?
Maybe 的替代实例如下:
instance Alternative Maybe where
empty = Nothing
Nothing <|> r = r
l <|> _ = l
它定义了 empty
和 (<|>)
,留下 some
和 many
作为它们的默认实现。
使用 many
和 some
是有意义的,因为 Alternative
可以成功或失败,因为 "external reasons" 不包含在值本身中。典型的例子是解析器:您尝试从输入流中重复解析整数,直到找不到整数并返回 empty
。
但是可以说 Just 2
,替代 "always succeeds"。值之外没有任何东西可以使它 "fail" 并完成计算。所以它进入了无限循环。
我正在查看 haskell 中的 Alternative
类型类,当我发布这个
some (Just 2)
挂了,我看了Alternative的源码,Alternative的很多默认定义是这样的:
some :: f a -> f [a]
some v = some_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
-- | Zero or more.
many :: f a -> f [a]
many v = many_v
where
many_v = some_v <|> pure []
some_v = (fmap (:) v) <*> many_v
很明显,some_v
和many_v
是间接无限递归的,它们不是根据empty
和<|>
定义的。
如果它们必须由实例定义,那么它们不应该有默认定义,对吧?由于 Maybe
没有定义它们,所以我上面的陈述被绞死了,这对我来说很奇怪,因为文档中没有提到它。
那么为什么要这样定义它们呢?有什么我想念的吗?
Maybe 的替代实例如下:
instance Alternative Maybe where
empty = Nothing
Nothing <|> r = r
l <|> _ = l
它定义了 empty
和 (<|>)
,留下 some
和 many
作为它们的默认实现。
使用 many
和 some
是有意义的,因为 Alternative
可以成功或失败,因为 "external reasons" 不包含在值本身中。典型的例子是解析器:您尝试从输入流中重复解析整数,直到找不到整数并返回 empty
。
但是可以说 Just 2
,替代 "always succeeds"。值之外没有任何东西可以使它 "fail" 并完成计算。所以它进入了无限循环。