问题标签 [applicative]

编辑更完整的问题：

我想创建一个解析器（我正在使用 uu-parsinglib），它获取前一个解析器的结果，如果结果包含某个构造函数，则有条件地失败：

我现在意识到这一定是一个单子解析器。

我有一个包含非直接左递归的语法。下图说明了问题，实际情况稍微复杂一些：

大多数时候我只对 Field 感兴趣，并且为了尽量减少回溯，最好专注于这种情况。

我已经定义了一个运算符来帮助

我将问题处理为：

注意我已经定义了一个 pChainl 的变体，它允许传入初始字段，同时保持左关联。

我想定义的问题

就 pField 而言，如果最右边的 Field 构造函数不是 Field_A，则后过滤器将失败。正如已经正确指出的那样，这是一个单子解析。我找不到任何使用 uu-parsinglib 作为 monadic 解析器的令人信服的例子，那么你建议的方法是什么？

如果我叫错了树，也请告诉我。

我想有一个类型的函数：

例如

catMaybes :: [Maybe a] -> [a]和in差不多Data.Maybe，只是catMaybes忽略了Nothing，而myf是很认真的Nothing。我可以f以一种天真的方式实现（如下所示），但想知道是否有更惯用的方式（如“应用函子”）：

或者

我遇到了这样一种情况，我的代码可以从使用Functor和Applicative类似的抽象中受益，但是对于 kind 类型(* -> *) -> *。可以RankNTypes像这样定义更高种类的函子

但更高版本的Applicative有点棘手。这是我能想到的最好的：

我们需要:->wrapper 类型才能使用 kind 函数，* -> *但这并不能让我们像普通 Applicatives 那样很好地链接函数应用程序。我可以使用助手进行管理，例如<$><*>

但是最好有一种通用的方法来“提升”任何数量的功能。

如何使用上述实例的一些简单示例：

所以，我的问题是：上面提到的类型类是什么，它们是否已经由 hackage 中的某个库提供？通过谷歌搜索，我想出了Functor2inlinear-maps和HFunctorin ，multi-rec但也不是我需要的。

另外，是否有某种方法可以在HApplicative没有:->包装器的情况下进行编写，或者是否有其他方法可以使功能提升更容易？

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

一个或多个：

零个或多个：

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

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

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

介绍

Scala Future（2.10和现在 2.9.3中的新功能）是一个应用函子，这意味着如果我们有一个可遍历的类型 F，我们可以将一个F[A]和一个函数A => Future[B]转换为一个Future[F[B]].

此操作在标准库中作为Future.traverse. Scalaz 7还提供了一个更通用的方法，如果我们从库traverse中导入 applicative functor 实例，我们可以在这里使用它。Futurescalaz-contrib

这两种traverse方法在流的情况下表现不同。标准库遍历在返回之前消耗流，而 Scalaz立即返回未来：

正如Leif Warner在这里所观察到的，还有另一个不同之处。标准库traverse立即启动所有异步操作，而 Scalaz 启动第一个，等待它完成，启动第二个，等待它，依此类推。

流的不同行为

通过编写一个函数，该函数将为流中的第一个值休眠几秒钟，很容易显示第二个区别：

现在Future.traverse(Stream(1, 2))(toFuture)将打印以下内容：

Scalaz 版本 ( Stream(1, 2).traverse(toFuture))：

这可能不是我们想要的。

对于列表？

奇怪的是，这两个遍历在列表上的这方面表现相同——Scalaz 不会在开始下一个未来之前等待一个未来完成。

另一个未来

Scalaz 还包括自己的concurrent包和自己的期货实现。我们可以使用与上述相同的设置：

然后我们得到 Scalaz 在列表和流的流上的行为：

也许不那么令人惊讶的是，遍历无限流仍然会立即返回。

问题

此时我们确实需要一个表格来总结，但必须要有一个列表：

• 带标准库遍历的流：在返回前消费；不要等待每个未来。
• 带有Scalaz遍历的流：立即返回；等待每个未来完成。
• Scalaz 带有流的期货：立即返回；等待每个未来完成。

和：

• 具有标准库遍历的列表：不要等待。
• 带有 Scalaz 遍历的列表：不要等待。
• 带有列表的 Scalaz 期货：请等待每个未来完成。

这有道理吗？列表和流上的此操作是否存在“正确”行为？是否有某种原因，“最异步”的行为——即在返回之前不要使用集合，并且不要等待每个未来完成后再继续下一个——这里没有表示？

ZipList comes with a Functor and an Applicative instance (Control.Applicative) but why not Alternative?

• Is there no good instance?
• What about the one proposed below?
  • Is it flawed?
  • is it useless?
  • Are there other reasonable possibilities (like Bool can be a monoid in two ways) and therefore neither should be the instance?

I searched for "instance Alternative ZipList" (with the quotes to find code first) and only found the library, some tutorials, lecture notes yet no actual instance.

Matt Fenwick said ZipList A will only be a monoid if A is (see here). Lists are monoids though, regardless of the element type.

This other answer by AndrewC to the same question discusses how an Alternative instance might look like. He says

There are two sensible choices for Zip [1,3,4] <|> Zip [10,20,30,40]:

1. Zip [1,3,4] because it's first - consistent with Maybe
2. Zip [10,20,30,40] because it's longest - consistent with Zip [] being discarded

where Zip is basically ZipList.

I think the answer should be Zip [1,3,4,40]. Let's see the instance:

The only Zip a we can produce without knowing the type argument a is Zip [] :: Zip a, so there is little choice for empty. If the empty list is the neutral element of the monoid, we might be tempted to use list concatenation. However, go is not (++) because of the drop 1. Every time we use one entry of the first argument list, we drop one off the second as well. Thus we have a kind of overlay: The left argument list hides the beginning of the right one (or all of it).

One intuition behind ziplists is processes: A finite or infinite stream of results. When zipping, we combine streams, which is reflected by the Applicative instance. When the end of the list is reached, the stream doesn't produce further elements. This is where the Alternative instance comes in handy: we can name a concurrent replacement (alternative, really), taking over as soon as the default process terminates.

For example we could write fmap Just foo <|> pure Nothing to wrap every element of the ziplist foo into a Just and continue with Nothing afterwards. The resulting ziplist is infinite, reverting to a default value after all (real) values have been used up. This could of course be done by hand, by appending an infinite list inside the Zip constructor. Yet the above is more elegant and does not assume knowledge of constructors, leading to higher code reusability.

We don't need any assumption on the element type (like being a monoid itself). At the same time the definition is not trivial (as (<|>) = const would be). It makes use of the list structure by pattern matching on the first argument.

The definition of <|> given above is associative and the empty list really is the empty element. We have

so all the laws you could ask for are satisfied (which is not true for list concatenation).

This instance is consistent with the one for Maybe: choice is biased to the left, yet when the left argument is unable to produce a value, the right argument takes over. The functions

are morphisms of alternatives (meaning psi x <|> psi y = psi (x <|> y) and psi x <*> psi y = psi (x <*> y)).

Edit: For the some/many methods I'd guess

Sorry for the terrible title. I'm trying to make an instance of Applicative for a Monad wrapping a type that is a Monoid.

This doesn't work; GCHi complains with:

I realise that what I've written above may make no sense. Here is the context: I am trying to use the compos abstraction as described in the paper A pattern for almost compositional functions. Taking this tree (using the GADT version of compos; I've simplified it a lot):

I'm going to write a lot of functions which descend the tree and return a list of say errors or a set of strings whilst also requiring state as it goes down (such as the binding environment), such as:

I think these should all be able to be abstracted away by making composFoldM use compos for the (Monad m, Monoid o) => m o structure. So to use it with the GADT Applicative version of compos found on page 575/576 of the paper. I think I need to make an Applicative instance of this structure. How would I do this? Or am I going down completely the wrong path?

在一次讨论中，我听说Applicative某些解析器的接口实现方式不同，比它们的Monad接口更有效。原因是Applicative我们在运行整个有效计算之前提前知道所有“效果”。对于 monad，效果可能取决于计算期间的值，因此无法进行这种优化。

我想看看这方面的一些好例子。它可以是一些非常简单的解析器或一些不同的 monad，这并不重要。重要的是Applicative这样一个 monad 的接口符合它的returnand ap，但使用Applicative产生更有效的代码。

更新：澄清一下，在这里我对不能是单子的应用程序不感兴趣。问题是关于两者兼而有之的事情。

使用时Data.Traversable，我经常需要一些代码，例如

遍历结构并建立一个由某种状态驱动的新结构。我注意到类型签名模式并相信它可以概括为

traverse但我无法用, sequenceA,fmap和<*>来实现这一点pure。也许我需要更强的类型类约束？我绝对需要Monad这里吗？

更新

具体来说，我想知道我是否可以定义fmapInner适用f于任何Traversable t适用于直觉的法则和一些适用于直觉的法则（我还不知道法则应该是什么），这是否暗示f事物是 a Monad？因为，对于Monads，实现是微不足道的：

更新

感谢您的出色回答。我发现我traverseF的只是

没有明确使用 Monad.State 并且所有对都翻转了。以前我虽然是这样，mapAccumR但实际上它是mapAccumL这样工作的traverseF。

我hoistFree从免费包推广到hoistFreeM，类似于如何推广fmap到Data.Traversable.mapM。

但是，我认为没有一种方法可以进一步推广它以与任何 一起工作Applicative，类似于如何推广Data.Traversable.mapM到Data.Traversable.traverse. 我对么？如果是这样，为什么？