सूचियों की सूचियों की सूची

Question

LoL a प्रकार का प्रतिनिधित्व करने का एक अच्छा तरीका क्या है, a के सूचियों की सूची होने के नाते? घोंसले का स्तर मनमाने ढंग से है, लेकिन बाहरी सूची के सभी तत्वों पर समान है।

मेरे मन में जो मामला है, वह सूची के सदस्यों पर एक समूह लागू करना है, और फिर प्रत्येक उपसमूह पर एक अगला समूह लागू करने के लिए, और इसी तरह। यह सामने नहीं है कि कितने समूह को आवेदन करना होगा। इसलिए: मैं-वें नंबर

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

के आधार पर

मान लीजिए deweyGroup i समूहों तत्वों:

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

rGroupBy ;-)

उदाहरण के प्रकार के हस्ताक्षर के लिए अतिरिक्त ब्राउनी अंक देता है:

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

पोस्टस्क्रिप्ट

एक दिन बाद, हम 4 उत्कृष्ट और पूरक समाधान है। मैं जवाब से बहुत खुश हूं; आप सभी को धन्यवाद।

Answer 1

मेरा मानना ​​है कि निम्न उदाहरण क्या आपने सोचा था के पास होना चाहिए। सबसे पहले हम प्रकार के स्तर की प्राकृतिक संख्या घोषित करते हैं। फिर हम वैक्टर को परिभाषित करते हैं, जो उनकी लंबाई को प्रेत प्रकार के रूप में लेते हैं (Fixed-length vectors in Haskell, Part 1: Using GADTs देखें)। और फिर हम सूचियों की नेस्टेड सूचियों के लिए एक संरचना को परिभाषित करते हैं ... जो गहराई को प्रेत प्रकार के रूप में रखता है। अंत में हम सही ढंग से टाइप किए गए 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

आपके पास वास्तव में एक पेड़ है। एक पुनरावर्ती डेटा संरचना के साथ यह का प्रतिनिधित्व करने का प्रयास करें:

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

आप वर्दी गहराई को लागू करना चाहते हैं, वहाँ एक (काफी) मानक है कि बहुरूपी प्रत्यावर्तन को शामिल करने के लिए चाल है।

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

वास्तव में, प्रकार के रूप में परिभाषित किया गया है: क्या हम क्या करेंगे बता कितनी गहराई से नेस्टेड सूची है, तो एक अंतिम "यहाँ" गहराई से-नेस्टेड सूची के साथ निर्माता "गहरा" निर्माताओं की एक रीढ़ की हड्डी है एक सौंदर्य विकल्प जो आप अपने कोड में बदलना चाहते हैं: Here कन्स्ट्रक्टर एक a लेता है और a एस की सूची नहीं है। इस विकल्प के परिणाम इस उत्तर के बाकी हिस्सों के माध्यम से बिखरे हुए हैं।

यहां इस प्रकार के सूचियों की सूचियों के प्रदर्शन का एक उदाहरण दिया गया है;

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

यहां पर कुछ नमूना कार्यों को देखने के है: यह दो Deeper कंस्ट्रक्टर्स गहराई-दो के लिए इसी घोंसला बनाने से यह है कि है।

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

एक और तरीका है बाधा है कि सभी शाखाओं बराबर गहराई है लागू करने के लिए एक नेस्टेड डेटाप्रकार उपयोग करने के लिए है:

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 5

एक प्रकार-hackery अभ्यास के रूप में प्राप्त करने के लिए यह मानक सूचियों के साथ इस लागू करने के लिए संभव है।

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

कौन इस तरह काम करता है::

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

तो हम सीधे हालांकि यह उलटे क्रम में डाल दिया जाना है इस सुविधा का उपयोग कर सकते हैं (

हम सभी की जरूरत है एक मनमाना गहराई groupStringsBy समारोह है):

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 

लेकिन यदि आप अपने मूल नमूना का उपयोग करना चाहते हैं, तो हम इसे भी हैक कर सकते हैं।

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 

निर्माण इस तरह::

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

पहले हम एक चर तर्क समारोह जो पाइपलाइनों सभी तर्कों लेकिन . के माध्यम से उलटे क्रम में पिछले एक है और फिर अंतिम तर्क पर लागू होता है, जिसके परिणामस्वरूप समारोह की जरूरत है

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) 

और अंत में w:

तो हमारे विधेय प्रकार type Pred = String -> String -> Bool के लिए कोई कस्टम नियम के साथ विस्तार rGroupBy में यह रैप (आपूर्ति id समारोह पाइप लाइन में प्रथम माना जाता है):

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

अब यह आपूर्ति की विधेय की संख्या के बराबर गहराई की सूची का निर्माण प्रकार Pred की विधेय समूहीकरण के किसी भी संख्या के लिए काम करना चाहिए :

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

तो यह संभव है (और शायद सरल किया जा सकता है), लेकिन हमेशा की तरह hackery की इस तरह के साथ कुछ भी लेकिन व्यायाम के लिए प्रयोग की जाने वाली अनुशंसित नहीं है।