2

indexJ問題があります。バランスの取れたバイナリ ツリーを各ステップでウォークスルーするときに、関数がどのサブツリーを選択する必要があるかをどのように決定する必要があるかわかりませんJoinList。

アイデアは、各サブツリーのサイズ (データ要素の数) をキャッシュすることです。これを各ステップで使用して、目的のインデックスが左または右のブランチにあるかどうかを判断できます。

私はこのコードを持っています:

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
                  deriving (Eq, Show)

newtype Size = Size Int
  deriving (Eq, Ord, Show, Num)

getSize :: Size -> Int
getSize (Size i) = i

class Sized a where
  size :: a -> Size

instance Sized Size where
  size = id

instance Monoid Size where
  mempty  = Size 0
  mappend = (+)

私は関数を書きます：

tag :: Monoid m => JoinList m a -> m
tag Empty = mempty
tag (Single x dt) = x
tag (Append x l_list r_list) = x

(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
(+++) jl1 jl2 = Append (mappend (tag jl1) (tag jl2)) jl1 jl2

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ i jl | i < 0 || (i+1) > (sizeJl jl) = Nothing 

  where sizeJl = getSize . size . tag

indexJ 0 (Single m d) = Just d
indexJ 0 (Append m (Single sz1 dt1) jl2) = Just dt1
indexJ i (Append m jl1 jl2) = if (sizeJl jl1) >= (sizeJl jl2) 
                              then indexJ (i-1) jl1  
                              else indexJ (i-1) jl2 

  where sizeJl = getSize . size . tag

関数tagと(+++)うまく機能していますがindexJ、JoinListツリーからi番目の要素を返す必要がある関数を終了する必要があります.i = [0..n]

私の機能indexJが間違っている =) 空のツリーがある場合 - (サイズ 0) シングル (サイズ 1) の「データ」がある場合 - (サイズ 1) ですが、Append (サイズ 2) (Single (Size 1) ) 'k') (シングル (サイズ 1) 'l') どのブランチを選択する必要がありますか? i-1 = 1 と i には、それぞれに 1 つのデータ要素を持つ 2 つのブランチがあります。

更新:誰かが JoinList のツリーのテイクアンドドロップ機能を必要とする場合、私はそれを作ります:

dropJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
dropJ _ Empty = Empty 
dropJ n jl | n <= 0 = jl
dropJ n jl | n >= (getSize . size $ tag jl) = Empty
dropJ n (Append m jL1 jL2)
  | n == s1 = jL2
  | n < s1 = (dropJ n jL1) +++ jL2
  | otherwise = dropJ (n - s1) jL2
                where s1 = getSize . size $ tag jL1

takeJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
takeJ _ Empty = Empty 
takeJ n jl | n <= 0 = Empty
takeJ n jl | n >= (getSize . size $ tag jl) = jl
takeJ n (Append m jL1 jL2)
  | n == s1 = jL1
  | n < s1 = (takeJ n jL1)
  | otherwise = jL1 +++ takeJ (n - s1) jL2
                where s1 = getSize . size $ tag jL1
4

2 に答える 2

6

私は

Append m joinList1 joinList2

の要素はjoinList1最初のインデックスを取り、その後に の要素が続きjoinList2ます。

次に、インデックスを作成するときに

indexJ i (Append m jL1 jL2)

iのサイズと比較する必要がありますjL1- と呼びましょうs1。の要素はjL10 から までのインデックスを占め、s1 - 1の要素はからまでjL2のインデックスを占めます。s1s1 + s2 - 1

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty  = Nothing
indexJ i (Single m d)
    | i == 0    = Just d
    | otherwise = Nothing
indexJ i (Append m jL1 jL2)
    | i < 0     = Nothing
    | i >= getSize (size m) = Nothing     -- optional, more efficient to have it
    | i < s1    = indexJ i jL1
    | otherwise = indexJ (i - s1) jL2
      where
        s1 = getSize . size $ tag jL1

インデックスが より小さい場合s1は最初のサブリストを調べ、それ以外の場合は 2 番目のサブリストを調べます。

于 2013-05-10T13:32:54.683 に答える