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

Question

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

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

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

用n的重复a,这里n是一个大于零的整数.我想是每个函数映射f中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在F(a, b)同时进行.尽管Template Haskell可能能够为我提供合适的工具,但我对这样的解决方案并不感兴趣.我想找到一些纯粹的"类型魔法"方法来做到这一点.

有谁知道这是否可能？有人可能会指出我正确的方向吗？或者这是一个已知的"问题"已经解决了数十亿次,而我却无法找到解决方案？

Answer 1

我们只需要在这里挑选毒药.如果我们使用不太安全的pragma,我们可以得到更多的推理,反之亦然; 有很多组合.

第一:使用重叠实例,非函数作为基本情况,但不能处理多态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,但至少不能以一种简单的方式解决.)