Listas de listas de listas

Question

¿Cuál es una buena manera de representar el tipo LoL a, siendo una lista de listas de ... de a? El nivel de anidación es arbitrario, pero uniforme en todos los elementos de la lista externa.

El caso que tengo en mente es aplicar una agrupación en los miembros de una lista , y luego aplicar una próxima agrupación en cada subgrupo, y así sucesivamente. No se conoce desde el principio cuántos grupos tendrá que aplicar. Por lo tanto:

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

brownie puntos extra para la firma de tipo de rGroupBy ;-)

Ejemplo:

Supongamos deweyGroup i grupos los elementos de base en el número i-ésimo

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

da:

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

PostScript

Un día más tarde, tenemos 4 soluciones excelentes y complementarios. Estoy muy satisfecho con las respuestas; gracias a todos.

Answer 1

Creo que el siguiente ejemplo debe estar cerca de lo que tenía en mente. Primero declaramos los números naturales de nivel de tipo. Luego definimos los vectores, que tienen su longitud como un tipo fantasma (ver Fixed-length vectors in Haskell, Part 1: Using GADTs). Y luego definimos una estructura para listas anidadas de listas de ... que lleva la profundidad como un tipo fantasma. Finalmente podemos definir correctamente tipeado 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) 

Answer 2

Lo que realmente tiene es un árbol. Pruebe lo representa con una estructura de datos recursiva:

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

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

Si desea aplicar una profundidad uniforme, hay una (bastante) truco estándar de hacer que la participación de la recursividad polimórfica. Lo que vamos a hacer es tener una columna vertebral de constructores "más profundos" decir cuán profundamente anidado es la lista, a continuación, una final constructor "aquí" con la lista están anidadas:

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

En realidad, el tipo que tiene definido una opción estética que puede variar en su código: el constructor Here toma un solo a y no una lista de a s. Las consecuencias de esta elección están dispersas por el resto de esta respuesta.

Aquí hay un ejemplo de un valor de este tipo que muestra listas de listas; tiene dos constructores Deeper correspondientes a la profundidad de dos anidación que tiene:

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

aquí a ver un par de funciones de ejemplo.

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

Otra manera de hacer cumplir la restricción de que todas las ramas tienen la misma profundidad que es el uso de un tipo de datos anidada:

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 

La ampliación de la definición de LoL, vemos que de manera informal,

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

Entonces podemos decir, por ejemplo:

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

para volver

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

Answer 5

Como un ejercicio de tipo hackery es posible implementar esto con listas estándar.

Todo lo que necesitamos es una función de la profundidad groupStringsBy arbitraria:

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

que funciona como esto:

*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"]]] 

así que podemos usar esta función directamente (aunque tiene que ser puesto en orden inverso):

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 

Pero si quiere usar su muestra original, podemos hackearla también. Primero necesitamos una función de la variable argumento que las tuberías de todos los argumentos pero el último en el orden inverso a través de . y luego se aplica la función resultante para el último argumento:

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 

funciona así:

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

a continuación, expanda con una regla personalizada para nuestro tipo de predicados 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) 

Y finalmente w rap en rGroupBy (suministro de id función sea la primera en la tubería):

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

Ahora debería funcionar para cualquier número de agrupar predicados de tipo Pred que producen la lista de la profundidad igual al número de predicados suministrados :

-- 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 

lo que es posible (y, probablemente, se puede simplificar) pero como siempre con este tipo de hackery no está recomendado para ser utilizado para otra cosa que el ejercicio.