Listen von Listen von Listen

Question

Was ist eine gute Möglichkeit, den Typ LoL a, eine Liste von Listen von ... von a zu repräsentieren? Die Verschachtelungsebene ist beliebig, aber einheitlich über alle Elemente der äußeren Liste.

Der Fall, den ich im Auge habe, ist eine Gruppierung auf die Mitglieder einer Liste anzuwenden, und dann eine nächste Gruppierung auf jede Untergruppe anzuwenden, und so weiter. Es ist nicht von vorne bekannt, wie viele Gruppierungen man anwenden muss. Daraus folgt:

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

zusätzliche Pluspunkte für die Art der Unterschrift rGroupBy ;-)

Beispiel:

Angenommen deweyGroup i Gruppen, die die Elemente auf der Basis der i-ten Reihe

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

gibt:

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

Postscript

Einen Tag später, haben wir 4 ausgezeichnet und ergänzende Lösungen. Ich bin sehr zufrieden mit den Antworten. Danke euch allen.

Answer 1

Ich glaube, das folgende Beispiel der Nähe sein sollte, was Sie im Sinn hatte. Zuerst deklarieren wir natürliche Zahlen auf Typenebene. Dann definieren wir Vektoren, die ihre Länge als Phantom-Typ tragen (siehe Fixed-length vectors in Haskell, Part 1: Using GADTs). Und dann definieren wir eine Struktur für verschachtelte Listen von Listen von ..., die die Tiefe als Phantom-Typ tragen. Schließlich können wir korrekt eingegebene rGroupBy definieren.

{-# 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) 

Answer 2

Was Sie eigentlich haben, ist ein Baum. Versuchen darstellt, es mit einer rekursiven Datenstruktur:

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"] gibt:

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

Wenn Sie einheitliche Tiefe erzwingen mögen, gibt es einen (recht) Standard Trick zu tun, dass polymorphe Rekursion beteiligt ist. Was wir tun, ist ein Rückgrat von „tiefer“ Konstrukteure haben zu sagen, wie tief verschachtelt die Liste ist, dann ein abschließender „hier“ Konstruktor mit der tief verschachtelten Liste:

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

Eigentlich als der Typ hat definiert eine ästhetische Wahl, die Sie möglicherweise in Ihrem Code ändern möchten: die Here Konstruktor nimmt eine einzige a und nicht eine Liste von a s. Die Konsequenzen dieser Entscheidung sind durch den Rest dieser Antwort verstreut.

Hier ist ein Beispiel für einen Wert dieses Typs mit List-of-Listen; es hat zwei Deeper Konstrukteure auf die Tiefen zwei entsprechende Verschachtelung, dass sie aufweist:

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

Hier einige Beispielfunktionen.

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

Eine weitere Möglichkeit, die Einschränkung zu erzwingen, dass alle Zweige gleiche Tiefe haben, ist einen verschachtelten Datentyp zu verwenden:

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 

die Definition von LoL Erweiterung, sehen wir, dass informell,

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

Dann können wir zum Beispiel sagen:

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

zurück zu bekommen

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

Answer 5

Als Typ-hackery Übung ist es möglich, dies mit Standardlisten zu implementieren.

Alles, was wir brauchen, ist eine beliebige Tiefe groupStringsBy Funktion:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, 
    UndecidableInstances, IncoherentInstances, 
    TypeFamilies, ScopedTypeVariables #-} 

import Data.List 
import Data.Function 

class StringGroupable a b where 
    groupStringBy :: Pred -> a -> b 

instance (StringGroupable a b, r ~ [b]) => StringGroupable [a] r where 
    groupStringBy f = map (groupStringBy f) 

instance (r ~ [[String]]) => StringGroupable [String] r where 
    groupStringBy p = groupBy p 

die wie folgt funktioniert:

*Main> let lst = ["11","11","22","1","2"] 
*Main> groupStringBy ((==) `on` length) lst 
[["11","11","22"],["1","2"]] 
*Main> groupStringBy (==) . groupStringBy ((==) `on` length) $ lst 
[[["11","11"],["22"]],[["1"],["2"]]] 

So können wir diese Funktion direkt verwenden (obwohl es in umgekehrter Reihenfolge gestellt werden muss,):

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

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

-- gives: [[["1.1"],["1.2.1","1.2.2"]],[["2.1"],["2.2"]],[["3"]]] 
test1 = groupStringBy (deweyGroup 2) . groupStringBy (deweyGroup 1) $ inp 

Aber wenn Sie Ihre ursprüngliche Probe verwenden möchten, können wir es auch hacken. Zuerst brauchen wir eine variable Argument Funktion, die Pipelines alle Argumente, aber die letzte in umgekehrter Reihenfolge über . und dann die resultierende Funktion auf das letzte Argument gilt:

class App a b c r where 
    app :: (a -> b) -> c -> r 

instance (b ~ c, App a d n r1, r ~ (n -> r1)) => App a b (c -> d) r where 
    app c f = \n -> app (f . c) n 

instance (a ~ c, r ~ b) => App a b c r where 
    app c a = c a 

funktioniert wie folgt:

*Main> app not not not True 
False 
*Main> app (+3) (*2) 2 
10 

Dann erweitern sie es für unser Prädikat-Typ mit einer benutzerdefinierten Regel type Pred = String -> String -> Bool:

type Pred = String -> String -> Bool 

instance (StringGroupable b c, App a c n r1, r ~ (n -> r1)) => App a b Pred r where 
    app c p = app ((groupStringBy p :: b -> c) . c) 

Und schließlich w rap es in rGroupBy (Versorgung id Funktion die erste in der Pipeline sein):

rGroupBy :: (App [String] [String] Pred r) => Pred -> r 
rGroupBy p = app (id :: [String] -> [String]) p 

Nun Pred Herstellung der Liste der Tiefe, die gleich der Anzahl der gelieferten Prädikate der Gruppierungs Prädikate der Art für eine beliebige Anzahl arbeiten sollte :

-- gives: [["1.1","1.2.1","1.2.2"],["2.1","2.2"],["3"]] 
test2 = rGroupBy (deweyGroup 1) inp 

-- gives: [[["1.1"],["1.2.1","1.2.2"]],[["2.1"],["2.2"]],[["3"]]] 
test3 = rGroupBy (deweyGroup 1) (deweyGroup 2) inp 

-- gives: [[[["1.1"]],[["1.2.1","1.2.2"]]],[[["2.1"]],[["2.2"]]],[[["3"]]]] 
test4 = rGroupBy (deweyGroup 1) (deweyGroup 2) (deweyGroup 1) inp 

so ist es möglich (und wahrscheinlich auch vereinfacht werden kann), aber wie immer mit dieser Art von Hacks wird nicht empfohlen, aber die Übung für alles verwendet werden.