Haskell

Question

在文章：“Write you a Haskell”（第 34 页）中，对“some”和“many”给出了以下解释：

Derived automatically from the Alternative typeclass definition are the many and some functions. many takes a single function argument and repeatedly applies it until the function fails, and then yields the collected results up to that point. The some function behaves similar except that it will fail itself if there is not at least a single match.

-- | One or more.
some :: f a -> f [a]
some v = some_v
  where
    many_v = some_v <|> pure []
    some_v = (:) <$> v <*> many_v

-- | Zero or more.
many :: f a -> f [a]
many v = many_v
  where
    many_v = some_v <|> pure []
    some_v = (:) <$> v <*> many_v

一段时间以来，我一直在努力理解这个实现。

我不明白“many”和“some”如何应用于"lists"或“Maybe”。

我也不确定 (:) <$> v <*> many_v。

如何得出这一结论？

Answer 1

从ghc/libraries/base/GHC/Base.hs开始有这个递归声明：

    ... :: f a -> f [a]
    ...
        many_v = some_v <|> pure []
        some_v = liftA2 (:) v many_v  -- (:) <$> v <*> many_v

参数 v 必须是类型的实例的值 Alternative（以及 Applicative 和 Functor）。 v 已经解除，只需要应用 (<*>)。该应用程序生成了一个提升列表。

some 和 many 递归应用 v 的构造函数，并将构造的值放入列表中。

some 在构建第一个 empty 时停止应用程序
many 继续申请

[] 是 Alternative:

的实例

instance Alternative [] where
    empty = []
    (<|>) = (++)

some 尝试列表：

  av = [[2], [2,3], [], [2,3,5]]
  some av                      -- no error, but never stops
  do {v <- some av; return v;} -- no error, but never stops

与 letter 相比 What are Alternative's "some" and "many" useful for?:

  import Control.Monad(Functor(..))
  import Control.Applicative
  import Data.Char
  newtype P a = P { runP :: String -> [(a,String)] }
  instance Functor P where
    fmap f (P q) = P (\s -> [ (f y,ys) | (y,ys) <- q s])
  instance Applicative P where
    pure x = P (\s -> [(x,s)])
    P p <*> P q = P (\s -> [(x y, ys) | (x,xs) <- p s, (y,ys) <- q xs])
  letter = P p where
    p (x:xs) | isAlpha x = [(x,xs)]
    p _ = []
  instance Alternative P where
    P p <|> P q = P (\s-> p s ++ q s)
    empty = P (\s-> [])

使用情况：

  runP (many letter) "ab123"

letter 是一个聪明的构造函数，即使用局部变量 p 构造具有字段 runP 的值 P。（访问器的结果）runP 是一个函数。 P 是一个实现 Alternative 的类型，也是一个构造函数。 P代表解析器。

fmap 未在 some 和 many 中使用。 <*> 导致函数 runP 的应用，谁的论据还没有在这里。基本上 some 和 many 构建了一个程序，该程序将从其参数中获取信息。参数必须是一个列表。由于懒惰，递归在第一个构造函数处停止。

  p = some letter -- constructs a program accessed via @runP@
  runP p "a1" -- [("a","1")]

  q = some [2] -- basically also a program
  q -- never stops

递归应用不是empty（[] for list），因为没有停止条件的来源，即没有输入。

这些停止：

  some [] -- []
  many [] -- [[]]
  some Nothing -- Nothing
  many Nothing -- Just []

some和many(v)的参数要求比较高

v 是 Alternative.
v类型的构造函数的递归应用必须停止在empty。
v 必须包含在构造期间应用的函数 <*> 才能具有停止条件。

结论： some 和 many 不能应用于列表值，即使列表实现 Alternative.

为什么 list 实现 Alternative？我想，就是在Applicative之上加上Monoid接口<|>和empty，不是因为 some 和 many.

  foldr (<|>) [] [[2],[],[3,4]] -- [2,3,4]

some 和 many 似乎只是为了解析器构造或者更一般地构造一个消耗输入的程序并产生更多产出，其中一些可以 empty。那已经很笼统了。但是在Alternative的位置才说得过去，如果大多数 Alternative 个实例对它都有合理的用途。事实并非如此。

Haskell - 一些，很多实现

Haskell - some, many implementation

some-and-many

alternative-functor