如何定义多重合成功能？

Question

有没有办法定义一个Haskell函数,它接受一个(某种类型的集合)函数并产生一个函数:它们的组成从右到左？

我试过了:

foldr ($)

但这只接受一个函数列表,其结果与其参数的类型相同:

foldr ($) :: a -> [a -> a] -> a

所以,我可以这样做:

foldr ($) 5 [(+) 1, (*) 2] 这会产生正确的结果11

然而,试图评估这个:

foldr ($) "hello" [(+) 1, length]

产生以下错误:

错误 - 列表中键入错误

*** Expression : [(1 +),length] *** Term : length *** Type : [a] -> Int *** Does not match : Int -> Int

Answer 1

像往常一样,让我们​​把类型注释放在任何地方.

-- foldr ($) "hello" [(+) 1, length]
($) :: (a -> b) -> a -> b
"hello" :: [Char]
(+) 1 :: Num a => a -> a
length :: [a] -> Int
[(+) 1, length] :: ?!

本机Haskell列表不能包含不同类型的项目.

所以让我们退一步吧.我将使用<并>表示"我们想要的清单." 我们不希望收集随机类型的东西.< (+) 1, length >没关系,但< length, (+) 1 >不是,或者说我们需要一个实例Num [a].同样,如果我们有两个以上的项目:每个项目的类型必然与其邻居相关.此外,整个列表的类型仅与第一个和最后一个成员的类型相关:什么是起始类型和结束类型？

我们可以用GADT做到这一点:

{-# 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

该值f是您所需的< (+) 1, length >"列表"的实现.

有一些进一步阐述Fpossible-- Functor和Category实例,例如-但我实在看不出多大用处吧.我们所做的就是人为地在普通函数组合上强加数据结构.我们甚至不能使用GHC的重载列表表示法,这不是(还是？)足够灵活.此外,插入所有GADT构造函数将阻止优化,几乎可以肯定包括列表融合.(我没有仔细试验或仔细考虑过.)

回答你的问题

是的,可以定义一个Haskell函数,该函数接受各种函数的集合,这些函数具有不同但可组合的类型,并生成它们的组合.我演示的集合类型需要GADTs扩展,这在您似乎正在使用的编译器Hugs中不可用.此外,你不能真正做这个集合.我没有证明这一点,但我会断言,除了通过模式匹配将其分解为组件函数之外,F a b对类型值不能用类型值做任何事情都无法做到a -> b.

换句话说,你所询问的内容在Haskell中确实是可以表达的,只是不清楚以这种方式做这件事有什么好处.

其他问题

正如我们在评论中所讨论的那样,您似乎正在为Clojure传感器寻找Haskell类比.你想就这个话题开一个新问题吗？它比这个更精确,更有针对性.

底线

为什么不用((+) 1) . length？