Pezzi nidificatiDi Haskell?

Question

dire che io voglio fare questo:

nestedChunksOf [3, 2] [1,1,1,2,2,2,3,3,3,4,4,4] == [[[1,1,1], [2,2,2]], [[3,3,3], [4,4,4]]] 

In Python, posso fare questo

def group(a, *ns): 
    for n in ns: 
     a = [a[i:i+n] for i in xrange(0, len(a), n)] 
    return a 

group([1,1,1,2,2,2,3,3,3,4,4,4], 3, 2) == [[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]] 

Ma in Haskell, non posso solo dire

nestedChunksOf :: [Int] -> [a] -> [[a]] 

o

nestedChunksOf :: [Int] -> [a] -> [[[a]]] 

Quindi, come posso ottenere la stessa cosa in Haskell?

Answer 1

Può essere fatto abbastanza facilmente con tipi dipendenti.

Vorremmo esprimere che la lunghezza dell'argomento [Int] determina il tipo del risultato. Dobbiamo due cose per cui: un tipo elenco di lunghezza fissa, e una funzione di tipo-livello che calcola il tipo di ritorno dalla lunghezza:

{-# LANGUAGE DataKinds, GADTs, TypeFamilies #-} 

import Data.List.Split 

data Nat = Z | S Nat -- natural numbers (zero, successor) 

data Vec n a where -- "n" length lists of "a" elements 
    Nil :: Vec Z a 
    (:>) :: a -> Vec n a -> Vec (S n) a 
infixr 5 :> 

type family Iterate n f a where 
    Iterate Z  f a = a 
    Iterate (S n) f a = f (Iterate n f a) 

Iterate n f a applica il costruttore di tipo fn volte ad un argomento. Ad esempio, Iterate (S (S Z)) [] Int si riduce a [[Int]]. nestedChunksOf si può scrivere direttamente ora:

nestedChunksOf :: Vec n Int -> [a] -> Iterate (S n) [] a 
nestedChunksOf Nil  as = as 
nestedChunksOf (n :> ns) as = chunksOf n $ nestedChunksOf ns as 

Usage:

> nestedChunksOf (2 :> 3 :> Nil) [1,1,1,2,2,2,3,3,3,4,4,4] 
[[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]] 

Answer 2

Una funzione come nestedChunksOf non può essere eseguita direttamente in Haskell, almeno non quella che funziona su liste normali. La profondità dell'elenco è parte del tipo, quindi non è possibile avere una profondità arbitraria specificata da un parametro.

Ma quello che si può fare è nidificare chunksOf.

Se definiamo chunksOf così:

chunksOf :: Int -> [a] -> [[a]] 
chunksOf _ [] = [] 
chunksOf n xs = fxs : chunksOf n sxs 
    where (fxs, sxs) = splitAt n xs 

Possiamo quindi nido è:

Main> :l test.hs 
[1 of 1] Compiling Main    (test.hs, interpreted) 
Ok, modules loaded: Main. 
*Main> chunksOf 3 [1,1,1,2,2,2,3,3,3,4,4,4] 
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]] 
*Main> chunksOf 2 $ chunksOf 3 [1,1,1,2,2,2,3,3,3,4,4,4] 
[[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]] 

Spero che compie quello che volevi!

Answer 3

Questo non può essere ottenuto in Haskell tramite "normale" vuol dire che richiederebbe un tipo dipendente - il tipo del risultato dipende dalla lunghezza del primo argomento.

Forse una soluzione di tuple sarebbe accettabile?

{-# Language TypeFamilies #-} 
{-# Language FlexibleInstances #-} 
import Data.List.Split 
class NestedChunksOf a where 
    nco :: a -> [b] -> AList a b 
    type AList a b :: * 

instance NestedChunksOf (Int,Int) where 
    nco (f,s) xs = chunksOf f (chunksOf s xs) 
    type AList (Int,Int) a = [[[a]]] 


-- More instances as desired. 

Answer 4

Come indicato nelle altre risposte, questo non può essere fatto direttamente come in Haskell è sempre necessario conoscere il tipo di espressione e quindi distinguere tra [a], [[a]] ecc.Tuttavia, utilizzando polymorphic recursion è possibile definire un tipo di dati che consente tale nidificazione arbitraria avvolgendo ogni livello in un costruttore:

data NestedList a = Value a | Nested (NestedList [a]) 
    deriving (Show) 

Quindi, solo Value è isomorfo a a, Nested (Value ...) è isomorfo a [a], doppia Nested-[[a]] etc. quindi è possibile implementare

chunksOf :: Int -> [a] -> [[a]] 
... 

nestedChunksOf :: [Int] -> [a] -> NestedList a 
nestedChunksOf [] xs = Nested (Value xs) 
nestedChunksOf (c:cs) xs = Nested (nestedChunksOf cs $ chunksOf c xs) 

E infatti

print $ nestedChunksOf [3, 2] [1,1,1,2,2,2,3,3,3,4,4,4] 

uscite

Nested (Nested (Nested (Value [[[1,1,1],[2,2,2]],[[3,3,3],[4,4,4]]])))