使用通用函数在异构数据结构上进行映射

Question

我正在研究一个HList实现,我不得不尝试map为它实现一个函数.我已经尝试了很多不同的方法,但是每个方法都会遇到与该函数相关的编译器错误.

以下是我希望如何使用泛型函数Just将其应用于输入数据结构的所有元素的示例.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

-- | An input heterogenous data structure
recursivePairs :: (Int, (Char, (Bool, ())))
recursivePairs = (1, ('a', (True, ())))

-- | This is how I want to use it
recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool, ())))
recursivePairs' = hMap Just recursivePairs

class HMap f input output where
  hMap :: f -> input -> output

-- | A counterpart of a Nil pattern match for a list
instance HMap f () () where
  hMap _ _ = ()

-- | A counterpart of a Cons pattern match for a list
instance 
  ( HMap f iTail oTail, 
    Apply f iHead oHead ) =>
  HMap f (iHead, iTail) (oHead, oTail) 
  where
    hMap f (head, tail) = (apply f head, hMap f tail)

class Apply f input output where
  apply :: f -> input -> output

instance Apply (input -> output) input output where
  apply = id

有了这个,我得到以下编译器错误:

No instance for (Apply (a0 -> Maybe a0) Int (Maybe Int))
  arising from a use of `hMap'
The type variable `a0' is ambiguous

有没有办法解决这个问题,如果没有,那么为什么呢？

Answer 1

问题是您尝试使用具有不同参数的多态函数,但您的Apply实例需要一个函数(单声道类型).您可以轻松地修复这种方式

data JustIfy = JustIfy
instance Apply JustIfy a (Maybe a) where
  apply _ = Just

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool, ())))
recursivePairs' = hMap JustIfy recursivePairs

与您的代码一起使用就好了

编辑:对同一事情更通用的方法是(要求RankNTypes)

--A "universal" action that works on all types
newtype Univ f = Univ (forall x. x -> f x)
instance Apply (Univ f) x (f x) where
   apply (Univ f) x = f x

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool, ())))
recursivePairs' = hMap (Univ Just) recursivePairs

或者如果您使用的是最新版本的GHC并且愿意开启更多扩展程序

newtype Univ' c f = Univ' (forall x. c x => x -> f x)
instance c x => Apply (Univ' c f) x (f x) where
  apply (Univ' f) x = f x

class All x
instance All x

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool, ())))
recursivePairs' = hMap (Univ' Just :: Univ' All Maybe) recursivePairs

这是很好的,从那以后它可以让你做一些事情,比如在你映射的函数中包含一个"show".

有关更通用的解决方案,请查看Oleg的Type级别lambda caclulus,它允许您在值级别编写代码,然后自动神奇地推断出相应的类型级别程序.不幸的是,Oleg的解决方案在这一点上相当陈旧,并使用了我并不特别喜欢的LC的标称实现.我一直在考虑如何做得更好,但可能会延迟到类型家庭的可靠平等.

我认为,现在HLists应该使用GADT和DataKinds而不是元组来完成.类型族优于函数依赖,但目前更有限,因为它们缺乏可判定的相等性.