51

Alternative, 的扩展Applicative, 声明empty,<|>和这两个函数：

一个或多个：

some :: f a -> f [a]

零个或多个：

many :: f a -> f [a]

如果定义，some并且many应该是方程的最小解：

some v = (:) <$> v <*> many v

many v = some v <|> pure []

我找不到定义some和的实例many。它们的意义和实际用途是什么？它们完全被使用了吗？仅仅从这个定义我就无法理解他们的目的。

更新：我不是在问什么是Alternative，只是什么是some和many

4

5 回答 5

22

TL;DR： some是一个或多个，是通过熟悉的最大咀嚼规则many一遍又一遍地执行相同的计算收集到的 0 个或多个结果。为了使这一点有意义，必须发生某种状态传递（和更改）以某种方式减少可能性域，否则它将无限重复。而状态传递和解析是密切相关的。

一个基本的例子：with

import Control.Monad(Functor(..))
import Control.Applicative
import Data.Char

-- char string parser
newtype P a = P { runP :: String -> [(a,String)] }

-- runP (P p) s = p s

instance Functor P where
  -- fmap :: (a -> b) -> f a -> f b
  fmap f (P q) = P (\s -> [ (f y,ys) | (y,ys) <- q s])

instance Applicative P where
  -- pure :: a -> f a
  pure x = P (\s -> [(x,s)])
  -- (<*>) :: f (a -> b) -> f a -> f b
  P p <*> P q = P (\s -> [(x y, ys) | (x,xs) <- p s, (y,ys) <- q xs])

letter = P p where      -- sample parser
  p (x:xs) | isAlpha x = [(x,xs)]
  p _ = []

我们有

*Main Data.Char> runP letter "123"
[]
*Main Data.Char> runP letter "a123"
[('a',"123")]
*Main Data.Char> runP ( (:) <$> letter <*> pure []) "a123"
[("a","123")]
*Main Data.Char> runP ( (:) <$> letter <*> ((:)<$>letter <*> pure []) ) "a123"
[]
*Main Data.Char> runP ( (:) <$> letter <*> ((:)<$>letter <*> pure []) ) "ab123"
[("ab","123")]   -- NOT NICE ^^^^^^^^^^^^^^^^^^^^ -}

然后，与

instance Alternative P where
  -- (<|>) :: f a -> f a -> f a
  P p <|> P q = P (\s-> p s ++ q s)
  -- empty :: f a   -- the identity of <|>
  empty = P (\s-> [])

我们得到

*Main Data.Char> runP (many letter) "ab123"
[("ab","123"),("a","b123"),("","ab123")]
*Main Data.Char> runP (some letter) "ab123"
[("ab","123"),("a","b123")]

*Main Data.Char> runP (optional letter) "ab123"
[(Just 'a',"b123"),(Nothing,"ab123")]
*Main Data.Char> runP (optional letter) "123"
[(Nothing,"123")]

Prelude Main Data.Traversable> runP (sequenceA $ replicate 2 letter) "ab123"
[("ab","123")]               --  NICE  ^^^^^^^^^^^^^^^^^^^
-}
于 2013-08-07T18:12:27.050 回答
17

在 STM Applicative 中，some这意味着：继续尝试直到成功至少一次，然后继续尝试直到失败。 many意思是：尽可能多地这样做，直到失败。

于 2013-08-07T21:36:44.603 回答
16

我倾向于在Applicative解析器组合库中看到它们。

a :: Parser [String]
a = some (string "hello")

我在 in 的默认定义中看到用于many目的。Parsingparsers

我认为 Parsec 是解析器组合库的主要示例，它隐藏了some/的使用，many因为它重新定义了(<|>).

于 2013-08-07T17:25:38.490 回答
5

Will 提供了一个很好的例子来激励使用这些方法，但是您似乎仍然对类型类有误解。

类型类定义列出了该类型类的所有实例存在的方法的类型签名。它还可能提供这些方法的默认实现，这就是 Alternative 的一些和许多方法正在发生的事情。

为了成为有效的实例，必须为实例定义所有方法。因此，您发现没有专门为某些或许多定义实例的那些使用默认实现，并且它们的代码与您的问题中列出的完全相同。

因此，为了清楚起见，由于类型类定义给出的默认定义，确实定义了一些和许多实例，并且可以与所有Alternative实例一起使用。

于 2013-08-07T20:08:37.437 回答
2

该regex-applicative包为（正则表达式）类型定义了一个自定义many方法。RE正则表达式和RE解析器的大小必须是有限的，因此对两者都使用默认定义some会many导致无限循环！幸运的是，many只是经典的正则表达式*。

该包还包含 的定义some，但它看起来太像默认定义，没有什么有趣的。

于 2020-06-17T16:53:32.903 回答