haskell - 在 Haskell 中实现函数加法

Question

在 Haskell 中，我得到了一个难题来执行以下操作，

f takes two functions, function a and function b. Function a takes n_a inputs and returns a Num type and function b takes n_b inputs and returns a Num type. f returns a new function of arity n_a+n_b that applies a to the first n_a arguments, n_b to the rest of the arguments and returns their sum.

在数学中，我会这样写:



我在 Haskell 中第一次天真的尝试是:

f a b = flip ((+) . a) . b

但这仅适用于 a是一元函数。

在这之后，我想了很久这个谜题，甚至无法想出我应该如何做到这一点的想法。这是很长一段时间以来我第一次在 Haskell 中完全被难住了。

我该如何解决这个难题？这个谜题有解决方案吗？ (一个 friend 给了我这个难题，我不相信他们当时有真正的解决方案)

Answer 1

这是一个非常简单的方法，使用在数字类型中单态工作的类型族(例如，专用于 Int )。我们需要一些扩展:

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE InstanceSigs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}

函数 f将在类型类中定义:

class VarArgs r s where
  type F r s
  f :: r -> s -> F r s

我们将处理以下情况。如果第一个函数的类型是 a :: Int -> r ，我们将使用以下实例来吞噬参数 x并将其提供给 a :

instance VarArgs r s => VarArgs (Int -> r) s where
  type F (Int -> r) s = Int -> F r s
  f :: (Int -> r) -> s -> Int -> F r s
  f a b x = f (a x) b

这对 a 的类型具有递归的效果。直到它的形式为 Int .然后，我们将使用一个类似的实例来递归 b :: Int -> s 类型。 :

instance VarArgs Int s => VarArgs Int (Int -> s) where
  type F Int (Int -> s) = Int -> F Int s
  f :: Int -> (Int -> s) -> Int -> F Int s
  f a b x = f a (b x)

最终，这两个函数都将简化为 a, b :: Int 类型的 0 元函数。 ，我们可以使用终端实例:

instance VarArgs Int Int where
  type F Int Int = Int
  f :: Int -> Int -> Int
  f a b = a + b

这里有一个小测试来证明它有效:

times2 :: Int -> Int -> Int
times2 x y = x * y
times3 :: Int -> Int -> Int -> Int
times3 x y z = x * y * z

foo :: [Int]
foo = [ f times2 times2 1 2 3 4
      , f times2 times3 1 2 3 4 5
      , f times3 times2 1 2 3 4 5
      , f times3 times3 1 2 3 4 5 6]

并将其加载到 GHCi 中给出:

> foo
[14,62,26,126]
>

将其概括为任何 Num 中的多态性类型似乎并不简单。更换 Int带有约束 Num n 的类型type 导致有关冲突族实例声明的错误。