Mercurial > hg > Members > atton > haskell > reflection_without_remorse

annotate diffList.hs @ 2:eccc7eced616 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add foldr style diffList
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Sat, 05 Jul 2014 19:08:19 +0900
parents 0251da3f04f2
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 -- Reflection without Remorse
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 -- http://homepages.cwi.nl/~ploeg/papers/zseq.pdf
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 -- https://github.com/atzeus/reflectionwithoutremorse
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 -- try implement diff list
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 type DiffList a = [a] -> [a]
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 absFromDiffList :: DiffList a -> [a] -- original name = abs
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 absFromDiffList a = a []
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 rep :: [a] -> DiffList a
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 rep = (++)
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 (+++) :: DiffList a -> DiffList a -> DiffList a
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 (+++) = (.)
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 list = replicate 10000 'a'
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 normalList = replicate 1000 list -- [l1, list2, list3, ..., listn]
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 diffList = map rep normalList -- [(++ list1), (++ list2), (++ list3), ..., (++ listn)]
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
1
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
23 normalListLeftLength = length $ foldl1 (++) normalList
0
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 -- length $ list1 ++ list2 ++ list3 ++ ... ++ listn
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 -- length $ ((list1 ++ list2) ++ list3) ++ ... ++ listn -- left associated
1
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
26 --
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
27 normalListRightLength = length $ foldr1 (++) normalList
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
28 -- length $ list1 ++ list2 ++ list3 ++ ... ++ listn
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
29 -- length $ (list1 ++ (list2 ++ (list3 ++ ... ++ listn))) -- right associated
0
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
1
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
31 diffListLeftLength = length $ absFromDiffList $ foldl1 (+++) diffList
0
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 -- length $ absFromDiffList $ (++ list1) +++ (++ list2) +++ (++ list3) +++ ... +++ (++ listn)
1
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
33 -- length $ absFromDiffList $ (((++ list1) +++ (++ list2)) +++ (++ list3)) +++ ... +++ (++ listn)
2
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
34 -- length $ absFromDiffList $ ((((++ list1) . (++ list2)) . (++ list3)) . ... . (++ listn) -- (++ list1)) = \x -> list1 ++ x
0
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 -- length $ absFromDiffList $ (++ (list1 ++ (list2 ++ (list3 ++ (...)))))
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 -- length $ (++ (list1 ++ (list2 ++ (list3 ++ (...))))) []
e96206b5d9c8 Implement DiffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 -- length $ (list1 ++ (list2 ++ (list3 ++ (...)))) ++ []
2
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
38 -- length $ ((list1 ++ (list2 ++ (list3 ++ (...)))) ++ []) -- right associated
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
39
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
40 diffListRightLength = length $ absFromDiffList $ foldr1 (+++) diffList
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
41 -- length $ absFromDiffList $ (++ list1) +++ (++ list2) +++ (++ list3) +++ ... +++ (++ listn)
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
42 -- length $ absFromDiffList $ ((++ list1) +++ ((++ list2) +++ ((++ list3) +++ ... +++ (++ listn))))
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
43 -- length $ absFromDiffList $ ((++ list1) . ((++ list2) . ((++ list3) . ... . (++ listn))))
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
44 -- length $ absFromDiffList $ (++ (list1 ++ (list2 ++ (list3 ++ (...)))))
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
45 -- length $ (++ (list1 ++ (list2 ++ (list3 ++ (...))))) []
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
46 -- length $ ((list1 ++ (list2 ++ (list3 ++ (...)))) ++ []) -- right associated
1
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
47
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
48
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
49 -- normalListRightLength -- ok
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
50 -- normalListLeftLength -- slowly
0251da3f04f2 Add foldr version
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
51 -- diffListLeftLength -- ok
2
eccc7eced616 Add foldr style diffList
Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
52 -- diffListRightLength -- ok