嵌套函数应用程序

Question

定义像这样的运算符非常容易

(@) :: [x -> y] -> [x] -> [y]

它获取函数列表和输入列表,并返回输出列表.有两种明显的方法可以实现这一点:

1. 将第一个函数应用于第一个输入,将第二个函数应用于第二个输入,等等.
2. 将每个功能应用于每个输入.

要么定义也同样微不足道.关于它的好处是你现在可以做类似的事情

foo :: X -> Y -> Z -> R

bar :: [X] -> [Y] -> [Z] -> [R]
bar xs ys zs = [foo] @@ xs @@ ys @@ zs

这概括为任意数量的函数参数.

---

到现在为止还挺好.现在针对问题:如何更改类型签名以@@使类型签名bar变为

bar :: [X] -> [Y] -> [Z] -> [[[R]]]

实现这种类型的函数并不难; 其中任何一个都会这样做:

bar xs ys zs = map (\ x -> map (\ y -> map (\ z -> foo x y z) zs) ys) zs
bar xs ys zs = map (\ z -> map (\ y -> map (\ x -> foo x y z) xs) ys) zs

我对于得到的结果并不挑剔.但我无法弄清楚如何调整@@运算符来做到这一点.

---

一个显而易见的尝试是

(@@) :: [x -> y] -> [x] -> [[y]]

实现这一点并不难,但它对你没有帮助.现在你有了

[foo] @@ xs :: [[Y -> Z -> R]]

这不是有效的输入@@.没有明显的方法可以知道有多少级别的列表可以通过该功能获得; 显然这种方法是死路一条.

我已经尝试了其他几种可能的类型签名,但没有一个让我更接近答案.有人可以给我一个解决方案,或解释为什么不存在？

Answer 1

你已经找到了为什么这很麻烦.你的功能(@@)被应用到不同类型的输入(例如[x->y],[[x -> y]]等这意味着您的类型签名@@是太严格,你将需要添加一些多态性,使其更通用,足以与嵌套列表使用它,因为哈斯克尔实现多态性.对于类型类,这是一个很好的尝试方向.

碰巧,如果您知道LHS的类型,则可以解决此问题,您可以唯一地确定RHS和结果.当输入有类型时[a->b],RHS必须是[a],结果必须是[[b]].这可以简化为a->bRHS 的输入[a]和结果[b].由于LHS确定了其他参数和结果,我们可以使用fundeps或类型族来表示其他类型.

{-# LANGUAGE TypeFamilies, UndecidableInstances #-}

class Apply inp where
  type Left inp    :: *
  type Result  inp :: *
  (@@) :: inp -> [Left inp] -> [Result inp]

现在我们有了一个类型类,我们可以为函数创建一个明显的实例:

instance Apply (a -> b) where
  type Left (a -> b)   = a
  type Result (a -> b) = b
  (@@) = map

列表实例也不错:

instance Apply f => Apply [f] where
  type Left [f]   = Left f
  type Result [f] = [Result f]
  l @@ r = map (\f -> f @@ r) l
  -- or    map (@@ r) l

现在我们的类方法@@应该适用于任意深度列表.以下是一些测试:

*Main> (+) @@ [1..3] @@ [10..13]
[[11,12,13,14],[12,13,14,15],[13,14,15,16]]'s

let foo :: Int -> Char -> Char -> String
    foo a b c = b:c:show a

*Main> foo @@ [1,2] @@ "ab" @@ "de"
[[["ad1","ae1"],["bd1","be1"]],[["ad2","ae2"],["bd2","be2"]]]

您可能希望查看printf实现以获得进一步的灵感.

编辑:发布后不久,我意识到可以将我Apply班级中的容器类型概括List为a Applicative,然后使用applicative instance而不是map.这将允许常规列表和ZipList行为.

Answer 2

实际上,这根本不需要类型类!通过避免类型类,你会失去一些方便,但这就是全部.

关键点在于,尽管重用了单个组合子,但多态性允许每种用法的类型不同.这与背后Applicative风格的表达式相同f <$> xs <*> ys <*> zs,这里的最终结果看起来很相似.因此,我们将为任何Functor而不仅仅是列表执行此操作.

这和Applicative版本之间的区别在于我们在Functor每一步都深入嵌套.必要的多态性需要最内层的灵活性,因此为了实现这一点,我们将使用continuation-ish技巧,其中每个组合器的结果是接受在最内层使用的变换的函数.

我们需要两个运算符,一个启动链,另一个继续递增.从后者开始:

(@@) :: (Functor f) => (((a -> b) -> f c) -> r) -> f a -> (b -> c) -> r
q  @@ xs = \k -> q (\f -> k . f <$> xs)

这会在右侧采用新参数,在左侧采用正在进行的表达式.结果需要一个函数k,它指定了如何获得最终结果.k与已经存在的表达式组合在一起,并且两者都映射在新参数上.这是令人费解的,但对于那些将CPS风格的代码分开的人来说应该看起来很熟悉.

(<@) :: (Functor f, Functor g) => f (a -> b) -> g a -> (b -> c) -> f (g c)
fs <@ xs = (<$> fs) @@ xs

通过简单地映射第一个参数上的所有其他内容来启动链.

与更简单的Applicative情况不同,我们还需要明确地结束链.与Contmonad一样,最简单的方法是将结果应用于identity函数.我们将给出一个有用的名称:

nested = ($ id)

现在,我们可以做这样的事情:

test2 :: [X -> Y -> R] -> [X] -> [Y] -> [[[R]]]
test2 fs xs ys = nested (fs <@ xs @@ ys)

test3 :: [X -> Y -> Z -> R] -> [X] -> [Y] -> [Z] -> [[[[R]]]]
test3 fs xs ys zs = nested (fs <@ xs @@ ys @@ zs)

不像类型类版本那么漂亮,但它可以工作.