列表清单列表

Question

什么是表示类型的好方法LoL a,是...的列表列表a？嵌套级别是任意的,但在外部列表的所有元素上是统一的.

我想到的情况是对列表成员应用分组,然后在每个子组上应用下一个分组,依此类推.事先不知道有多少人必须申请.因此:

rGroupBy :: [(a -> a -> Bool)] -> [a] -> [...[a]...]

额外的布朗尼点为类型签名rGroupBy;-)

例:

假设deweyGroup i基于第i个数字对元素进行分组

rGroupBy [deweyGroup 1, deweyGroup 2] 
         ["1.1", "1.2.1", "1.2.2", "2.1", "2.2", "3"]

得到:

[ [ [ "1.1" ], [ "1.2.1", "1.2.2" ] ],
  [ [ "2.1" ], [ "2.2" ] ],
  [ [ "3" ] ]
]

后记

一天后,我们有4个优秀的互补解决方案.我很满意答案; 谢谢你们.

Answer 1

强制所有分支具有相同深度的约束的另一种方法是使用嵌套数据类型:

data LoL a = One [a] | Many (LoL [a])

mapLoL :: ([a] -> [b]) -> LoL a -> LoL b
mapLoL f (One xs) = One (f xs)
mapLoL f (Many l) = Many $ mapLoL (map f) l

rGroupBy :: [a -> a -> Bool] -> [a] -> LoL a
rGroupBy [] xs = One xs
rGroupBy (f:fs) xs = Many $ mapLoL (groupBy f) $ rGroupBy fs xs

扩大定义LoL,我们非正式地看到,

LoL a = [a] | [[a]] | [[[a]]] | ...

然后我们可以说,例如:

ghci> rGroupBy [(==) `on` fst, (==) `on` (fst . snd)] [ (i,(j,k)) | i<-[1..3], j<-[1..3], k<-[1..3]]

去取回

Many (Many (One [[[(1,(1,1)),(1,(1,2)),(1,(1,3))]],[[(1,(2,1)),(1,(2,2)),(1,(2,3)), ...

Answer 2

你实际拥有的是一棵树.尝试用递归数据结构表示它:

data LoL a = SoL [a] | MoL [LoL a] deriving (Eq, Show)

rGroupBy :: [(a -> a -> Bool)] -> [a] -> LoL a
rGroupBy (f:fs) = MoL . map (rGroupBy fs) . groupBy f
rGroupBy []     = SoL

deweyGroup :: Int -> String -> String -> Bool
deweyGroup i a b = a!!idx == b!!idx where idx = 2*(i-1)

rGroupBy [deweyGroup 1, deweyGroup 2] ["1.1", "1.2.1", "1.2.2", "2.1", "2.2", "3.0"] 得到:

MoL [MoL [SoL ["1.1"],
          SoL ["1.2.1","1.2.2"]],
     MoL [SoL ["2.1"],
          SoL ["2.2"]],
     MoL [SoL ["3.0"]]
    ]

Answer 3

如果你想强制统一深度,有一个(相当)标准的技巧来做涉及多态递归.我们要做的是有一个"更深层"构造函数的主干,告诉列表有多深入嵌套,然后是一个带有深层嵌套列表的最终"here"构造函数:

data GroupList a = Deeper (GroupList [a]) | Here a deriving (Eq, Ord, Show, Read)

实际上,定义的类型有一个美学选择,您可能希望在代码中有所不同:Here构造函数只需要一个a而不是一个as 列表.这个选择的后果在这个答案的其余部分分散了.

以下是展示列表清单的此类价值的示例; 它有两个Deeper与深度二嵌套相对应的构造函数:

> :t Deeper (Deeper (Here [[1,2,3], []]))
Num a => GroupList a

这里有一些示例函数.

instance Functor GroupList where
    fmap f (Here   a ) = Here   (f a)
    fmap f (Deeper as) = Deeper (fmap (fmap f) as)
    -- the inner fmap is at []-type

-- this type signature is not optional
flatten :: GroupList [a] -> GroupList a
flatten (Here   a ) = Deeper (Here a)
flatten (Deeper as) = Deeper (flatten as)

singleGrouping :: (a -> a -> Bool) -> GroupList [a] -> GroupList [a]
singleGrouping f = flatten . fmap (groupBy f)

rGroupBy :: [a -> a -> Bool] -> [a] -> GroupList [a]
rGroupBy fs xs = foldr singleGrouping (Here xs) fs

Answer 4

我相信下面的例子应该接近你的想法。首先我们声明类型级自然数。然后我们定义向量，其长度作为幻像类型（请参阅Haskell 中的固定长度向量，第 1 部分：使用 GADT）。然后我们为......列表的嵌套列表定义一个结构，它将深度作为幻像类型。最后我们可以定义正确键入的rGroupBy.

{-# LANGUAGE GADTs #-}
{-# LANGUAGE EmptyDataDecls #-}

import Data.List (groupBy)

data Zero
data Succ n

data Vec n a where
    Nil  ::                 Vec Zero a
    Cons :: a -> Vec n a -> Vec (Succ n) a

data LList n a where
    Singleton :: a           -> LList Zero a
    SuccList  :: [LList n a] -> LList (Succ n) a

-- Not very efficient, but enough for this example.
instance Show a => Show (LList n a) where
    showsPrec _ (Singleton x)   = shows x
    showsPrec _ (SuccList lls)  = shows lls

rGroupBy :: Vec n (a -> a -> Bool) -> [a] -> LList (Succ n) a
rGroupBy Nil
    = SuccList . map Singleton
rGroupBy (Cons f fs)
    = SuccList . map (rGroupBy fs) . groupBy f

-- TEST ------------------------------------------------------------

main = do
    let input = ["1.1", "1.2.1", "1.2.2", "2.1", "2.2", "3"]

    -- don't split anything
    print $ rGroupBy Nil input
    -- split on 2 levels
    print $ rGroupBy (Cons (deweyGroup 1) 
                           (Cons (deweyGroup 2) Nil))
               input 
  where
    deweyGroup :: Int -> String -> String -> Bool
    deweyGroup i a b = a!!idx == b!!idx where idx = 2*(i-1)