-
Notifications
You must be signed in to change notification settings - Fork 0
/
Histogram.hs
86 lines (63 loc) · 3.35 KB
/
Histogram.hs
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
{-# Language FunctionalDependencies, MultiParamTypeClasses,
FlexibleInstances, UndecidableInstances, TypeOperators #-}
-- Histograms for use in huffman encoding
-- Ludvik 'Probie' Galois 2014
module Histogram where
import TypePrelude
-- We'll need binary search trees
data BinaryNull
data BinaryNode key val left right
class BinaryTree a
instance BinaryTree BinaryNull
instance (BinaryTree b, BinaryTree c) => BinaryTree (BinaryNode key a b c)
-- Let's insert values into binary search trees
class InsertIntoBinaryTree key val tree newTree | key val tree -> newTree where
insertIntoBinaryTree :: key -> val -> tree -> newTree
insertIntoBinaryTree = undefined
instance InsertIntoBinaryTree key val BinaryNull
(BinaryNode key val BinaryNull BinaryNull)
instance ( LEQ key key' lte, LEQ key' key gte, And lte gte eq, Not eq neq
, And lte neq lt, And gte neq gt, Is equalp (BinaryNode key val leftTree rightTree)
, If eq equalp compp res, InsertIntoBinaryTree key val leftTree leftTree'
, InsertIntoBinaryTree key val rightTree rightTree'
, If lte (BinaryNode key' val' leftTree' rightTree)
(BinaryNode key' val' leftTree rightTree') compp)
=> InsertIntoBinaryTree key val (BinaryNode key' val' leftTree rightTree) res
-- And have a specialised version for histograms
class InsertIntoHistogram key tree newTree | key tree -> newTree where
insertIntoHistogram :: key -> tree -> newTree
insertIntoHistogram = undefined
type EB1 = EightBit One Zero Zero Zero Zero Zero Zero Zero
-- val'' in the absence of val may seem weird.
-- tl;dr I copy pasted my above code
instance (Binary key) => InsertIntoHistogram key BinaryNull
(BinaryNode key (EightBit One Zero Zero Zero Zero Zero Zero Zero) BinaryNull BinaryNull)
instance ( Binary key, LEQ key key' lte, LEQ key' key gte, And lte gte eq, Not eq neq
, And lte neq lt, And gte neq gt, Is equalp (BinaryNode key val'' leftTree rightTree)
, Add val' EB1 val'', If eq equalp compp res, InsertIntoHistogram key leftTree leftTree'
, InsertIntoHistogram key rightTree rightTree'
, If lte (BinaryNode key' val' leftTree' rightTree)
(BinaryNode key' val' leftTree rightTree')
compp)
=> InsertIntoHistogram key (BinaryNode key' val' leftTree rightTree) res
-- Convert a list of bytes to a histogram
class ByteListToHistogram a b | a -> b where
byteListToHistogram :: a -> b
byteListToHistogram = undefined
instance (ByteListToHistogram' a BinaryNull b) => ByteListToHistogram a b
class ByteListToHistogram' a b c | a b -> c where
byteListToHistogram' :: a -> b -> c
byteListToHistogram' = undefined
instance ByteListToHistogram' Nil a a
instance (InsertIntoHistogram x tree tree', ByteListToHistogram' xs tree' res)
=> ByteListToHistogram' (x ::: xs) tree res
-- Find a value in a binary search tree
class Lookup key tree val | key tree -> val where
lookup :: key -> tree -> val
lookup = undefined
instance Lookup paths BinaryNull Nil
instance (Lookup key left leftRes, Lookup key right rightRes, LEQ key key' lte,
LEQ key' key gte, And lte gte eq, If lte leftRes rightRes neq, If eq val' neq res) =>
Lookup key (BinaryNode key' val' left right) res
emptyTree :: BinaryNull
emptyTree = undefined