如何定义一个多重组合函数？ [英] How to define a multiple composition function?
问题描述
是否有一种方法可以定义一个Haskell函数，该函数接受（某种类型的函数集合）函数并生成一个函数：从右到左的合成？
我试过：
foldr（$）
但这只接受一个函数列表，其结果与它们的参数具有相同的类型：
foldr（$）:: a - > [a - > a] - > a
所以，我可以这样做：
foldr（$）5 [（+）1，（*）2]
，并产生正确的结果11
然而，试图评估这一点：
$ b foldr（$）hello[（+ ）1，length]
产生以下错误：
错误 - 在列表中输入错误
***表达式：[（1 +），length]
***术语：长度
***类型：[a] - > Int
***不匹配：Int - > Int
与往常一样，让我们将类型注释放在任何地方。
- foldr（$）hello[（+）1，length]
（$）:: （a - > b） - > a - > b
hello:: [Char]
（+）1 :: Num a => a - > a
长度:: [a] - > Int
[（+）1，length] ::？！
原生Haskell列表不能包含不同类型的项目。
所以让我们回来一步。我将使用< 和> 来表示list-ish我们想要的东西。我们不想收集随机类型的东西。 < （+）1，长度> 可以，但< （+）1> 不是，或者我们需要一个实例 Num [a] 。同样，如果我们有两个以上的项目：每个项目的类型必然与其邻居有关。此外，整个列表的类型只与第一个和最后一个成员的类型有关：起始和结束类型是什么？
我们可以使用GADT来做到这一点：
{ - ＃LANGUAGE GADTs＃ - }
module SO26565306 where
data F ab其中
FNil :: F aa
（：&）::（b - > c） - > F a b - > F a c
infixr 5：&
runF :: F a b - > a - > b
runF FNil = id
runF（f：& fs）= f。 runF fs
f :: F [a] Int
f =（+）1：&长度：& FNil
ghci> runF fhello
6
值 f 是你想要的< （+）1，长度> list。
F 可能 - Functor 和 Category 实例 - 但我没有看到太多用处为了它。我们所做的只是人为地将数据结构强加于普通函数组合上。我们甚至无法使用GHC的重载列表符号，这不是（但？）足够灵活。此外，插入所有GADT构造函数将阻止优化，几乎可以肯定包括列表融合。 （我没有仔细试验或仔细考虑过。）
回答您的问题
是的，这是可能的定义一个Haskell函数，该函数接受不同但可组合的类型的函数集合，并生成它们的组合。我演示的集合类型需要 GADTs 扩展，它是中不可用，这是您似乎正在使用的编译器。此外，你无法真正对收藏做很多事情。我没有证明它，但我会断言你不能用类型 F ab 的值来完成， code> a - > b ，除了通过模式匹配把它分解成它的组件函数。
换句话说，你问的是确实可以表达的在Haskell中，目前还不清楚以这种方式做这件事有什么好处。
其他问题
正如我们在评论中所讨论的那样，您似乎在寻找Clojure换能器的哈斯克尔类比。你想开一个关于这个话题的新问题吗？它比这个更精确和集中。
底线
为什么不使用（（+）1）。长度？
Is there a way to define a Haskell function that takes a (some kind of collection) of functions and produces a single function: their composition from right to left?
I tried:
foldr ($)
but this only accepts a list of functions whose result has the same type as that of their argument:
foldr ($) :: a -> [a -> a] -> a
So, I can do:
foldr ($) 5 [(+) 1, (*) 2]
and this produces the correct result 11
However trying to evaluate this:
foldr ($) "hello" [(+) 1, length]
produces the error below:
ERROR - Type error in list
*** Expression : [(1 +),length]
*** Term : length
*** Type : [a] -> Int
*** Does not match : Int -> Int
As always, let's put type annotations everywhere.
-- foldr ($) "hello" [(+) 1, length]
($) :: (a -> b) -> a -> b
"hello" :: [Char]
(+) 1 :: Num a => a -> a
length :: [a] -> Int
[(+) 1, length] :: ?!
Native Haskell lists cannot contain items of different types.
So let's back up a step. I'll use < and > to denote "the list-ish thing we want." We don't want a collection of randomly-typed things. < (+) 1, length > is okay, but < length, (+) 1 > is not, or rather we'd need an instance Num [a]. Similarly if we have more than two items: each item's type is necessarily related to its neighbors. Furthermore, the type of the overall list is related only to the types of the first and last members: what's the starting and ending type?
We can do this with GADTs:
{-# LANGUAGE GADTs #-}
module SO26565306 where
data F a b where
FNil :: F a a
(:&) :: (b -> c) -> F a b -> F a c
infixr 5 :&
runF :: F a b -> a -> b
runF FNil = id
runF (f :& fs) = f . runF fs
f :: F [a] Int
f = (+) 1 :& length :& FNil
ghci> runF f "hello"
6
The value f is the implementation of your desired < (+) 1, length > "list".
There's some further elaboration of F possible--Functor and Category instances, for example--but I don't really see much use for it. All we've done is artificially impose a data structure on ordinary function composition. We can't even use GHC's overloaded list notation, which isn't (yet?) sufficiently flexible. Furthermore, interposing all the GADT constructors will block optimizations, almost certainly including list fusion. (I haven't experimented or thought through it carefully.)
Answering Your Question
Yes, it's possible to define a Haskell function that takes a collection of functions, of varying but composable types, and produces their composition. The collection type I've demonstrated needs the GADTs extension, which is not available in Hugs, the compiler you seem to be using. Furthermore, you can't really do much with the collection. I've not proved it, but I'll assert that there's nothing you can do with a value of type F a b that you can't do with a value of type a -> b, other than decomposing it into its component functions by pattern-matching.
In other words, what you're asking about is indeed expressible in Haskell, it's just not clear that there's any advantage to doing it in this way.
Other Questions
As we've discussed in the comments, it seems you're looking for a Haskell analogy for Clojure transducers. Would you like to open a new question on that topic? It's a bit more precise and focused differently than this one.
The Bottom Line
Why not just use ((+) 1) . length?
这篇关于如何定义一个多重组合函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
