haskell - 使用通用函数映射异构数据结构

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

这很好，因为它可以让你做一些事情，比如在你映射的函数中包含“显示”。

有关更通用的解决方案，请查看 Oleg's Type level lambda caclulus它允许您在值级别编写代码，然后自动推断出适当的类型级别程序。不幸的是，Oleg 的解决方案在这一点上相当陈旧，并且使用了我不太喜欢的 LC 的名义实现。我一直在考虑如何做得更好，但可能会推迟，直到类型家庭实现可判定的平等。

我的观点是，现在 HList 应该使用 GADT 和 DataKinds 而不是元组来完成。类型族比函数依赖更可取，但目前受到更多限制，因为它们缺乏可判定的相等性。