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

Question

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

给定两种类型，a, b考虑由该类型的函数组成的函数族F(a, b)。

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

使用n重复的a，其中n是大于零的整数。我想要的是将F(a, b)中的每个函数f' :: [a] -> b映射到一个函数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编写一个函数。尽管模板Haskell可能能够为我提供正确的工具，但我对这种解决方案并不感兴趣。我想找到一些纯粹的“类型魔法”的方式来做到这一点。

有人知道这是否可能吗？有人能给我指明正确的方向吗？或者，这是一个已知的“问题”，已经解决了数十亿次，而我只是无法找到解决办法？

Answer 1

我们只需要在这里挑选我们的毒药。如果我们使用不太安全的语用，我们可以得到更多的推论，反之亦然；有许多组合。

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

第四：使用带有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和类型家族作为语言扩展的争议最大，而且它们仍然提供了相当多的可用性。

Answer 2

实际上，它非常简单，甚至不需要重叠实例：

{-# 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来缓解这个问题，但至少不能简单地解决。)