Haskell: a -> a -> ... -> b 到 [a] -> b

Question

我正在尝试将以下地图表示为 Haskell 函数：

给定两种类型 a, b 考虑由

类型的函数组成的函数族 F(a, b)

f :: a -> a -> ... -> a -> b

n 次重复 a，其中 n 是一个大于零的整数。我想要的是将 F(a, b) 中的每个函数 f 映射到函数 f' :: [a] -> b，使得 f x1 x2 ... xr = f' [x1, ..., xr]，其中 r 小于参数数量 f 需要（即我正在寻找函数 listify :: F(a, b) -> ([a] -> b)）。如果元素多于 f 接受参数，则应丢弃额外的元素：

f :: a -> a -> b
(listify f xs) == (listify f $ take 2 xs)

此外，如果传递空列表，任何值都可以。

我当然能够为具有固定数量参数的函数（例如：listify :: (a -> a -> b) -> ([a] -> b) 等）实现此映射，但我找不到编写函数的方法同时对 F(a, b) 中的所有 f 执行此操作。尽管模板 Haskell 可能能够为我提供合适的工具，但我对这样的解决方案不感兴趣。我想找到一些纯粹的 "type magic" 方法来做到这一点。

有谁知道这是否可能？有人可以指出我正确的方向吗？或者这是一个已知的 "problem" 已经解决了数十亿次，我就是找不到解决方案？

Answer 1

其实很简单，甚至不需要重叠实例：

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Listifiable f a b where
  listify :: f -> [a] -> b

instance Listifiable b a b where
  listify = const

instance (Listifiable f) a b => Listifiable (a->f) a b where
  listify f (x:xs) = listify (f x) xs

那你可以做

GHCi> listify ((+) :: Int->Int->Int) [1,2 :: Int] :: Int
3

但是对这些本地显式类型签名的需求充分说明了您遇到的问题。

（使用 FunctionalDependencies 或许可以缓解这个问题，但至少不是直接的方式。）

Answer 2

我们只需要在这里挑选我们的毒药。如果我们使用不太安全的编译指示，我们可以获得更多的推断，反之亦然；有多种组合。

First：使用重叠实例，具有非函数作为基本情况，但无法处理多态 a 类型：

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- error
-- listify (+) [0, 2 :: Int] -- OK
-- listify () [] -- OK

其次：使用重叠实例，具有基本情况的功能，可以处理多态类型：

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

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where
  listify f (a:_) = f a

instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- OK
-- listify () [] -- error, first arg must be a function

第三种：使用不连贯的实例，在基本情况下具有值，可以处理多态类型：

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify 0 [] -- OK
-- listify (+) [2, 4] -- OK

Fourth：使用封闭类型族UndecidableInstances作为实例解析的助手，具有基本情况下的值，无法处理多态类型：

{-# LANGUAGE UndecidableInstances, ScopedTypeVariables, DataKinds,
    TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-}

import Data.Proxy

data Nat = Z | S Nat

type family Arity f where
  Arity (a -> b) = S (Arity b)
  Arity b        = Z

class Listify (n :: Nat) a b where
  listify' :: Proxy n -> a -> b

instance r ~ (a -> b) => Listify Z b r where
  listify' _ = const

instance (Listify n f r, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) a r where
  listify' _ f (a:as) = listify' (Proxy :: Proxy n) (f a) as

listify :: forall a b. Listify (Arity a) a b => a -> b
listify = listify' (Proxy :: Proxy (Arity a))

-- listify (+) [3, 4] -- error
-- listify (+) [3, 4::Int] -- OK
-- listify () [] -- OK
-- listify 0 [] -- error
-- listify (0 :: Int) [] -- OK

根据我的想法，大致这些是人们在野外可以看到的变体，INCOHERENT 变体除外，因为这在库代码中极为罕见（有充分的理由）。

我个人推荐带有封闭类型族的版本，因为 UndecidableInstances 和类型族作为语言扩展是迄今为止争议最小的，而且它们仍然提供了相当多的可用性。

Haskell: a -> a -> ... -> b 到 [a] -> b

Haskell: a -> a -> ... -> b to [a] -> b

haskell

types

higher-order-functions