3

我正在尝试编写一个函数，它将给定值附加到嵌套列表结构的最里面的列表中，但是当我什至不确定此类函数的类型签名是什么时，我遇到了类型错误.

digpend a xs = case xs of [_:_] -> map (digpend a) xs
                          [[]]  -> [[a]]
                          xs    -> a:xs

例如，

digpend 555 [ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ]

应该返回

[ [ [ 555,5,1,-12,33 ] , [ 555,6,22 ] ] , [ [ 555,-9,0,9,12,83 ] ] ]

理想情况下，它可以通过递归在任何级别的嵌套上工作。这是允许的吗？

4

3 回答 3

6

这是一个不完全令人满意的实现，使用类型类：

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class DigPend a b where
  digpend :: a -> [b] -> [b]

instance DigPend a a where
  digpend x xs = (x:xs)

instance (DigPend a b) => (DigPend a [b]) where
  digpend x xs = map (digpend x) xs

只要完全指定参数的类型，它就可以很好地工作：

*Main> digpend (5 :: Int) ([6,7,8] :: [Int])
[5,6,7,8]
*Main> digpend (555 :: Int) ([[[5,1,-12,33],[6,22]],[[-9,0,9,12,83]]] :: [[[Int]]])
[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]]
*Main> digpend (5 :: Int) ([] :: [Int])
[5]
*Main> digpend (5 :: Int) ([] :: [[Int]])
[]

然而，像这样的调用digpend 5 [6,7,8]会触发很多“模棱两可的类型变量”错误——像这样的数字文字5是多态的（它可以包含 的任何实例Num），虽然ghci通常会很高兴地默认为Integer，但它首先尝试解决 的类型类约束DigPend，并且在那个阶段，没有足够的类型信息让它知道digpend应用哪个实例。

于 2013-06-28T16:37:51.727 回答
4

解决这个问题需要一些类型级的编程技能和一些 GHC 扩展。

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE OverlappingInstances #-}

class Digpend a d where
  digpend :: a -> d -> d

instance (Digpend a d) => Digpend a [d] where
  digpend a list = map (digpend a) list

instance Digpend a [a] where
  digpend a list = a : list

main = do
  -- We have to help the compiler disambiguate the numbers by putting explicit
  -- type signatures:
  print $ digpend 
    (555 :: Int) 
    ([ [ [ 5,1,-12,33 ] , [ 6,22 ] ] , [ [ -9,0,9,12,83 ] ] ] :: [[[Int]]])
  -- In case of specific literals, such as `Char`, it's not a problem though.
  print $ digpend '!' [['a', 'b', 'c'], "def"]

结果是：

[[[555,5,1,-12,33],[555,6,22]],[[555,-9,0,9,12,83]]]
["!abc","!def"]
于 2013-06-28T16:34:21.197 回答
2

如果您可以/被允许定义自己的数据类型，您还可以使用以下内容：

data Tree a = Leaves [a] | InnerNodes [Tree a] deriving (Show)

digpend :: a -> Tree a -> Tree a
digpend x (Leaves xs) = Leaves $ x:xs
digpend x (InnerNodes []) = InnerNodes [Leaves [x]]
digpend x (InnerNodes xs) = InnerNodes . map (digpend x) $ xs

一些输出示例：

*Main> digpend 10 $ InnerNodes [ Leaves [], Leaves [], InnerNodes []]
InnerNodes [Leaves [10],Leaves [10],InnerNodes [Leaves [10]]]
*Main> digpend 555 $ InnerNodes [InnerNodes [Leaves [5, 1, -12, 33], Leaves [6, 22]], InnerNodes [Leaves [-9, 0, 9, 12, 83]]]
InnerNodes [InnerNodes [Leaves [555,5,1,-12,33],Leaves [555,6,22]],InnerNodes [Leaves [555,-9,0,9,12,83]]]
于 2013-06-28T17:27:05.880 回答