时间戳

首页 > 解决方案 > Haskell - 一些，很多实现

haskell - Haskell - 一些，很多实现

问题描述

在文章：“给你写一个 Haskellsome ”（第 34 页）中，给出了对“ ”和“ ”的以下解释many：

和函数自动从Alternative类型类定义派生而来。接受一个函数参数并重复应用它直到函数失败，然后产生收集到的结果。该函数的行为类似，但如果没有至少一个 匹配项，它将自行失败。manysomemanysome 

-- | 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”应用于“列表”或“ Maybe”。

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

这是如何得出的？

标签： haskellsome-and-manyalternative-functor

解决方案

从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(and Applicativeand 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

与Alternativeletter的 “一些”和“许多”有什么用处相比？：

  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带有字段的值。（访问器的结果）是一个函数。 是一个实现类型，也是一个构造函数。 代表解析器。runPprunPPAlternativeP

fmap不用于someand 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？我想，是把Monoid接口<|>加empty在上面Applicative，而不是因为someand many。

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

some并且many似乎仅用于解析器构造或更一般地构造消耗输入并产生更多输出的程序，其中一些可以是empty. 这已经很笼统了。但是只有在大多数情况下都有合理的用法时，这个地方Alternative才是合理的。Alternative事实并非如此。

推荐阅读