Revisions to Purely functional brodal heap implementation

deleted 78 characters in body

Source Link

edited Jun 30, 2018 at 22:03

3.8k
13
17

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  SkewA= ::SkewA { left_ :: Tree a l, right_ :: Tree a l }          -> SkewBinomial a l
  SkewB| ::SkewB { single_ :: a, linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l
  Binomial| ::Binomial            { linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l

data Tree a l = Tree a l deriving Functor
instance Ord a => Ord (Tree a l) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $
  let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }          -> SkewBinomial a l
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l
  Binomial ::            { linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l

data Tree a l = Tree a l deriving Functor
instance Ord a => Ord (Tree a l) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l
  = SkewA { left_ :: Tree a l, right_ :: Tree a l }
  | SkewB { single_ :: a, linked_ :: Tree a l, lower_ :: l }
  | Binomial            { linked_ :: Tree a l, lower_ :: l }

data Tree a l = Tree a l deriving Functor
instance Ord a => Ord (Tree a l) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1) $
  let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
  let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

added 60 characters in body

Source Link

edited Jun 30, 2018 at 21:55

Gurkenglas

3.8k
13
17

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  BinomialSkewA :: { linked_left_ :: Tree a l, lower_right_ :: Tree a l }          -> SkewBinomial a l
  SkewASkewB :: { left_single_ :: a, linked_ :: Tree a l, right_lower_ :: Treel } -> SkewBinomial a l }
  SkewBBinomial :: { single_ :: a,        { linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l

data Tree a l = Tree a l deriving Functor
 
instance Ord a => Ord (Tree a l) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  Binomial :: { linked_ :: Tree a l, lower_ :: l }
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l }

data Tree a l = Tree a l deriving Functor
 
instance Ord a => Ord (Tree a) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }          -> SkewBinomial a l
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l
  Binomial ::            { linked_ :: Tree a l, lower_ :: l } -> SkewBinomial a l

data Tree a l = Tree a l deriving Functor
instance Ord a => Ord (Tree a l) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

deleted 9 characters in body

Source Link

edited Jun 30, 2018 at 21:48

Gurkenglas

3.8k
13
17

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  Binomial :: { linked_ :: Tree a l, lower_ :: l }
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l }

data Tree a l = Tree a l deriving Functor

instance Ord a => Ord (Tree a) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree'combineTree leftt1 rightt2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [left[t1, right]t2] in
  fmap (Layer . BinomialSkewB el big) small

combineTree left right el = min (Tree el $ Layer $combineTree' SkewAt1 t2 t1)=
  $  let [small, big] = sort [t1, t2] in fmap (Layer . SkewB elBinomial big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  Binomial :: { linked_ :: Tree a l, lower_ :: l }
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l }

data Tree a l = Tree a l deriving Functor

instance Ord a => Ord (Tree a) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree' left right = let [small, big] = sort [left, right] in
  fmap (Layer . Binomial big) small

combineTree left right el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

Consider lens.

Field names need not indicate types, a good IDE makes that information available. Replace singleTree_ in SkewBLayer with the simpler el. SkewBinomialLayer decomposes:

data Layer f d where
  Layer0 :: Layer 0
  Layer :: KnownNat d => f (Layer f d) -> Layer f (d + 1)

data SkewBinomial a l where
  Binomial :: { linked_ :: Tree a l, lower_ :: l }
  SkewA :: { left_ :: Tree a l, right_ :: Tree a l }
  SkewB :: { single_ :: a, linked_ :: Tree a l, lower_ :: l }

data Tree a l = Tree a l deriving Functor

instance Ord a => Ord (Tree a) where compare = comparing skewData

type SkewBinomialLayer a = Layer (SkewBinomial a)

combineTree t1 t2 el = min (Tree el $ Layer $ SkewA t2 t1)
  $ let [small, big] = sort [t1, t2] in fmap (Layer . SkewB el big) small

combineTree' t1 t2 =
    let [small, big] = sort [t1, t2] in fmap (Layer . Binomial big) small

Consider lens.

edited body

Source Link

edited Jun 30, 2018 at 21:44

Gurkenglas

3.8k
13
17

Loading

added 957 characters in body

Source Link

edited Jun 30, 2018 at 21:41

Gurkenglas

3.8k
13
17

Loading

added 957 characters in body

Source Link

edited Jun 30, 2018 at 21:36

Gurkenglas

3.8k
13
17

Loading

added 957 characters in body

Source Link

edited Jun 30, 2018 at 21:31

Gurkenglas

3.8k
13
17

Loading

Source Link

answered Jun 30, 2018 at 20:37

Gurkenglas

3.8k
13
17

Loading

Stack Exchange Network

Return to Answer