mbrcknl

Initial call

bounce(append(List(1,2,3,4,5),List(6)))

Descend into argument

append(List(1,2,3,4,5),List(6))
bounce(...)

mbrcknl

Learning about trampolining in Scala.

I began with Ken Scambler's [YOW! Lambda Jam 2014 workshop][ws] on Free monads, but found that the simple formulation of Free derived in [exercise 1][ex1] was susceptible to stack overflow when used for trampolining in [exercise 2][ex2]. This is just an investigation into what causes this stack overflow, and how [scalaz][]'s [GoSub][] trick avoids it.

mbrcknl

-- Is Set.union better than O(n+m) in some cases?

import Criterion.Main (Benchmark, bench, bgroup, defaultMain, env, whnf)
import Data.Set (Set, fromList, union)

main :: IO ()
main = defaultMain [ bgroup "union" $ map benchUnion sizes ]

-- Grow Set size exponentially, under the hypothesis that
-- Set.union will be O(log n) in this special case.

mbrcknl

import Criterion.Main (Benchmark, bench, bgroup, defaultMain, env, whnf)
import Data.Foldable (Foldable(..),toList)
import Data.Maybe (Maybe(..))
import Data.Monoid (Monoid(..), (<>))
import Data.Set (Set,fromList)
import Prelude (Eq(..),Ord(..),Show(..),Int,(.),($),($!),Num(..),const,take,iterate,map,return,IO)

last :: Foldable t => t a -> Maybe a
last = foldl (const Just) Nothing

mbrcknl

Difference Lists

Proposed BFPG lightning talk. 25 slides, 5 minutes, 12 seconds per slide. No problem!

September 2014

1

Motivation: we want to write something as clear as this, but this is O(n^2).

mbrcknl

{-# LANGUAGE Rank2Types #-}

type Lens s t a b = forall f. Functor f => (a -> f b) -> (s -> f t)

type Ref s t a b = s -> Rep a b t
data Rep a b t = Rep a (b -> t)

instance Functor (Rep a b) where
  fmap f (Rep a g) = Rep a (f . g)

mbrcknl

{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE ImpredicativeTypes #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeOperators #-}

-- Richard Bird, Thinking Functionally with Haskell.
-- Chapter 2, Exercise E:

mbrcknl

{-# LANGUAGE RankNTypes #-}

import Control.Lens.Lens (Lens,lens)

type Quotient s t a = forall b. Lens s t a b

quotient :: (s -> a) -> (s -> t) -> Quotient s t a
quotient sa st = lens sa (const . st)

mbrcknl

Fixpoint split
           {X Y : Type} (l : list (X*Y))
           : (list X) * (list Y) :=
  match l with
    | nil => (nil, nil)
    | (x,y) :: t =>
      let (r,s) := split t in
      (x :: r, y :: s)
  end.

mbrcknl

Theorem combine_split : forall X Y (l : list (X * Y)) l1 l2,
  split l = (l1, l2) ->
  combine l1 l2 = l.
Proof.
  induction l as [|[x y] ps];
  try (simpl; destruct (split ps));
  inversion 1;
  try (simpl; apply f_equal; apply IHps);
  reflexivity.
Qed.