12

LoL aの...のリストのリストであるタイプを表す良い方法は何aですか？ネストレベルは任意ですが、外側のリストのすべての要素で均一です。

私が考えているのは、リストのメンバーにグループ化を適用してから、各サブグループに次のグループ化を適用するということです。いくつのグループを適用する必要があるかは、事前にはわかりません。したがって：

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

の型署名のための余分なブラウニーポイントrGroupBy;-)

例：

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

追記

1日後、4つの優れた補完的なソリューションがあります。私は答えにとても満足しています。皆さん、ありがとうございました。

4

5 に答える 5

13

すべてのブランチの深さが等しいという制約を適用する別の方法は、ネストされたデータ型を使用することです。

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)), ...
于 2012-08-07T21:22:35.593 に答える
10

あなたが実際に持っているのは木です。再帰的なデータ構造で表現してみてください。

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"]]
    ]
于 2012-08-07T17:58:51.083 に答える
7

均一な深さを強制したい場合は、多形再帰を含む（かなり）標準的なトリックがあります。ここでは、リストがどれだけ深くネストされているかを示す「より深い」コンストラクターのスパインを作成し、次に、深くネストされたリストを含む最後の「ここ」コンストラクターを作成します。

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

実際、定義されたタイプには、コード内で変更したい美的選択肢が1つあります。コンストラクターは、のリストではなく、Here単一のものを取ります。この選択の結果は、この回答の残りの部分に散らばっています。aa

これは、リストのリストを示すこのタイプの値の例です。Deeper深さに対応する2つのコンストラクターがあります-2つのネストがあります：

> :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
于 2012-08-07T21:18:45.217 に答える
3

次の例は、あなたが考えていたものに近いはずだと思います。まず、型レベルの自然数を宣言します。次に、ファントムタイプとして長さを持つベクトルを定義します（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)
于 2012-08-07T19:37:54.400 に答える
1

タイプハッカリーの演習として、これを標準リストで実装することができます。

必要なのは、任意の深さのgroupStringsBy関数だけです。

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

したがって、この関数を直接使用できます（ただし、逆の順序で配置する必要があります）。

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。

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)

そして最後にそれをラップします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

したがって、それは可能です（そしておそらく単純化することができます）が、いつものように、この種のハッカーは運動以外の目的で使用することはお勧めしません。

于 2012-08-09T04:15:30.497 に答える