Diff lists "too big a type"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
{-# OPTIONS_GHC -XRankNTypes #-}

module Main 
where

--- http://stackoverflow.com/questions/13346200/type-safe-difference-lists



newtype F a = F { runF :: forall r. r -> (a -> r -> r) -> r }

empty = F (\r g->r)
singleton x = F (\r g-> g x r)

{-
*Main> runF empty [1] (:)
[1]

*Main> runF (singleton 2) [1] (:)
[2,1]

*Main> runF (singleton 4) [3,2,1] (:)
[4,3,2,1]

*Main> runF (singleton 2) [1] (\a r->[a])
[2]

*Main> runF (singleton 4) [3,2,1] (\a r->a:reverse r)
[4,1,2,3]

-}

x4 = runF (singleton 4) [3,2,1] (\a r->a:reverse r)


fromList []     = empty         -- fromList [x] = singleton x

fromList (x:xs) = F (\r g-> g x $ runF (fromList xs) r g)


{-
*Main> runF (fromList [1..4]) [] (:)
[1,2,3,4]

*Main> runF (fromList [1..4]) [] (\a r->[a])
[1]

*Main> runF (fromList [1..4]) [] (\a r->a:reverse r)
[1,3,4,2]

*Main> runF (fromList [1..4]) [] (\a r->a:reverse r++r)
[1,4,4,3,3,4,4,2,2,4,4,3,3,4,4]

*Main> runF (append (fromList [1,2]) (fromList [3,4]))[] (\a r->a:reverse r++r)
[1,4,4,3,3,4,4,2,2,4,4,3,3,4,4]
                                 -- same result as above... OK we can argue that
                                 -- appending worked right, it's the reporting that
                                 -- is screwing things up here
-}


append a b = F (\r g-> runF a (runF b r g) g)     

toList a = runF a [] (:)


{-
*Main> toList (append (fromList [1..4]) (fromList [11..15]))
[1,2,3,4,11,12,13,14,15]



BUT!! IF we define    -- and the point it, WE *CAN* --
                      --   the proper chaining is NOT enforced by the type 
                      --   the `g` functions are "too loose"


> append a b = F (\r g-> runF b (runF a r g) g)       --- NB!! switched a/b <--> b/a


THEN


*Main> runF (append (fromList [1,2]) (fromList [3,4]))[] (\a r->a:reverse r++r)
[3,2,2,1,1,2,2,4,4,2,2,1,1,2,2]
                                 -- DIFFERENT RESULT!!! OK, we could argue that
                                 -- this "swapped" append is wrong for this kind of
                                 -- "reporting function" ut the point is, the type
                                 -- allowed us to do this... so this means it's "too big", right?


*Main> toList (append (fromList [1..4]) (fromList [11..15]))
[11,12,13,14,15,1,2,3,4]
-}

1:1: Error: Use better pragmas
Found:
{-# OPTIONS_GHC -XRankNTypes #-}
Why not:
{-# LANGUAGE RankNTypes #-}
12:12: Error: Use const
Found:
\ r g -> r
Why not:
const