Kgtkr's Blog

差分リスト式変形

2018/09/19
haskell

メモ

-- リスト(右結合)
[1,2,3,4,5] ++ ([6,7] ++ [8])
[1,2,3,4,5] ++ [6,7,8] -- コスト2(合計2)
[1,2,3,4,5,6,7,8] -- コスト5(合計7)

-- リスト(左結合)

([1,2,3,4,5] ++ [6,7]) ++ [8]
[1,2,3,4,5,6,7] ++ [8] -- コスト5(合計5)
[1,2,3,4,5,6,7,8] -- コスト7(合計12)


-- 差分リスト(右結合)
fromDiffList(toDiffList [1,2,3,4,5] <> (toDiffList [6,7] <> toDiffList [8]))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> ((\b->[6,7] ++ b) <> (\c->[8] ++ c)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->(\b->[6,7] ++ b) ((\c->[8] ++ c) x)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->(\b->[6,7] ++ b) ([8] ++ x)))
fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->[6,7] ++ ([8] ++ x)))
fromDiffList((\y->(\a->[1,2,3,4,5] ++ a)) ((\x->[6,7] ++ ([8] ++ x)) y))
fromDiffList((\y->(\a->[1,2,3,4,5] ++ a)) ([6,7] ++ ([8] ++ y)))
fromDiffList(\y->[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y)))
(\y->[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y))) []
[1,2,3,4,5] ++ ([6,7] ++ ([8] ++ []))
[1,2,3,4,5] ++ ([6,7] ++ [8]) -- コスト1(合計1)
[1,2,3,4,5] ++ [6,7,8] -- コスト2(合計3)
[1,2,3,4,5,6,7,8] -- コスト5(合計8)

-- 差分リスト(左結合)

fromDiffList((toDiffList [1,2,3,4,5] <> toDiffList [6,7]) <> toDiffList [8])
fromDiffList(((\a->[1,2,3,4,5] ++ a) <> (\b->[6,7] ++ b)) <> (\c->[8] ++ c))
fromDiffList((\x->(\a->[1,2,3,4,5] ++ a) ((\b->[6,7] ++ b) x)) <> (\c->[8] ++ c))
fromDiffList((\x->(\a->[1,2,3,4,5] ++ a) ([6,7] ++ x)) <> (\c->[8] ++ c))
fromDiffList((\x->([1,2,3,4,5] ++ ([6,7] ++ x))) <> (\c->[8] ++ c))
fromDiffList((\y->(\x->([1,2,3,4,5] ++ ([6,7] ++ x))) ((\c->[8] ++ c) y)))
fromDiffList((\y->(\x->([1,2,3,4,5] ++ ([6,7] ++ x))) ([8] ++ y)))
fromDiffList((\y->([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y)))))
(\y->([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ y))))
([1,2,3,4,5] ++ ([6,7] ++ ([8] ++ [])))
([1,2,3,4,5] ++ ([6,7] ++ [8])) -- コスト1(合計1)
([1,2,3,4,5] ++ [6,7,8]) -- コスト2(合計3)
[1,2,3,4,5,6,7,8] -- コスト5(合計8)