public
Last active

  • Download Gist
diff.hs
Haskell
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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
 
import Data.Function (on)
import Data.List (maximumBy)
 
 
class Container f where
data Context f :: * -> *
children :: f a -> [(a, Context f a)]
plugIn :: a -> Context f a -> f a
childAt :: f a -> Context f a -> a
 
newtype Rec f = Rec { runRec :: f (Rec f) }
 
deriving instance (Eq (f (Rec f))) => Eq (Rec f)
 
deriving instance (Show (f (Rec f))) => Show (Rec f)
 
type Step f = Context f (Rec f)
 
data Change f = Skip (Step f) | Take (Step f) | Replace (Rec f) (Rec f)
 
deriving instance (Show (Context f (Rec f)), Show (Rec f)) => Show (Change f)
 
type Path f = [Change f]
 
type InContext f = (Rec f, Path f)
 
subs :: (Container f) => Rec f -> [InContext f]
subs (Rec x) | null $ children x = [(Rec x, [])]
| otherwise = [ s | (x', ctx) <- children x,
(x'', ctxs) <- subs x',
s <- [(x'', Skip ctx:ctxs), (Rec $ plugIn x'' ctx, Take ctx:ctxs)] ]
 
type ChangeSet f = (Path f, Path f)
 
common :: (Container f, Eq (Rec f)) => [InContext f] -> [InContext f] -> [ChangeSet f]
common xs ys = [ (p1, p2) | (s1, p1) <- xs, (s2, p2) <- ys, s1 == s2 ]
 
takes :: Path f -> Path f
takes = filter take where
take (Take _) = True
take _ = False
 
size :: ChangeSet f -> Int
size (xs, ys) = length (takes xs) + length (takes ys)
 
largest :: [ChangeSet f] -> ChangeSet f
largest = maximumBy (compare `on` size)
 
diff :: (Container f, Eq (Rec f)) => Rec f -> Rec f -> ChangeSet f
diff old new = largest $ (common `on` subs) old new
 
 
patch :: (Container f, Eq (Rec f)) => Rec f -> ChangeSet f -> Rec f
patch old (inserts, deletes) = foldr wrap (unwrap old inserts) deletes where
wrap (Skip _) x = x
wrap (Take ctx) x = Rec $ plugIn x ctx
wrap (Replace x y) _ = y
unwrap x [] = x
unwrap x (Skip ctx:cs) = Rec $ plugIn (unwrap (childAt (runRec x) ctx) cs) ctx
unwrap x (Take ctx:cs) = unwrap (childAt (runRec x) ctx) cs
unwrap _ (Replace x y:cs) = unwrap x cs
 
 
 
 
 
 
diff2 :: (Container f, Eq (Context f (Rec f))) => Rec f -> Rec f -> ChangeSet f
diff2 old new
| null $ children $ runRec old = ([], [Replace old new])
| null $ children $ runRec new = ([Replace old new], [])
| otherwise = let matches = [ (x', y', ctx1)
| (x', ctx1) <- children $ runRec old
, (y', ctx2) <- children $ runRec new
, ctx1 == ctx2 ] in
if null matches then
largest $ [ let (xs, ys) = diff2 x' new in (Skip ctx:xs, ys)
| (x',ctx) <- children $ runRec old ] ++
[ let (xs, ys) = diff2 old y' in (xs, Skip ctx:ys)
| (y',ctx) <- children $ runRec new ]
else
largest [ let (xs, ys) = diff2 x' y' in (Take ctx:xs, Take ctx:ys)
| (x', y', ctx) <- matches ]
 
 
 
 
 
 
 
 
data ListF a x = Nil | Cons a x deriving (Show, Eq)
 
type List a = Rec (ListF a)
 
instance Container (ListF a) where
data Context (ListF a) x = ListContext a deriving (Show)
children Nil = []
children (Cons a x) = [(x, ListContext a)]
plugIn x (ListContext a) = Cons a x
childAt (Cons _ x) (ListContext _) = x
 
nil = Rec Nil
 
cons a x = Rec $ Cons a x
 
fromList = foldr cons nil
 
toList (Rec Nil) = []
toList (Rec (Cons a x)) = (a:toList x)
 
 
 
 
data ExprF x = App x x | Abst String x | Var String deriving (Show, Eq)
 
type Expr a = Rec ExprF
 
instance Container ExprF where
data Context ExprF x = AppContext (Either x x) | AbstContext String deriving (Show, Eq)
children (App f x) = [(f, AppContext $ Right x), (x, AppContext $ Left f)]
children (Abst i x) = [(x, AbstContext i)]
children (Var _) = []
plugIn x (AppContext (Left f)) = App f x
plugIn f (AppContext (Right x)) = App f x
plugIn x (AbstContext i) = Abst i x
childAt (App _ x) (AppContext (Left _)) = x
childAt (App f _) (AppContext (Right _)) = f
childAt (Abst _ x) (AbstContext _) = x
 
abst i x = Rec $ Abst i x
 
app f x = Rec $ App f x
 
var i = Rec $ Var i
 
k = abst "x" $ abst "y" $ var "x"
 
s = abst "x" $ abst "y" $ abst "z" $ app (app (var "x") (var "z")) (app (var "y") (var "z"))
 
silly =
(app
(app
(app
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var ""))))
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var "")))))
(app
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var ""))))
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var ""))))))
(app
(app
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var ""))))
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var "")))))
(app
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var ""))))
(app
(app
(app (var "") (var ""))
(app (var "") (var "")))
(app
(app (var "") (var ""))
(app (var "") (var "")))))))

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.