https://twitter.com/1HaskellADay/status/484197096749535232

haskell_a_day_2014_07_02.hs

module Data.Deque where

{--

The following sets of problems over the next few days get their inspiration
from some of the problems from the P99, or Ninety-Nine Prolog Problems
published by Werner Hett.

Create a traversable data type, let’s call it Deque a (‘Deque’ meaning:
‘double-ended queue’) such that the operation

last :: Deque a -> a

is in constant time, also have this function obey the properties of the
same-named function for lists, that is: it gives an error for an empty Deque.

That’s the ‘get.’ The ‘put’ for this type should also be in ‘kinda good’ time
at either end (see declarations below for prepend and postpend).

Bonus:

1. Prove (or show) that last (Deque a) is in constant time.

2. Prove, or show, that an implementation of Deque a can have

zweitletztes (Deque a)

such that zweitletztes (Deque a) is faster than

zweitletztes [a].

Explanation:

The last element of a list or deque is its ultimate element
The zweitletztes element of a list or deque is its penultimate element.

So, for let deck = dequeFromList [1..10]

last deck ~> 10
zweitletztes deck ~> 9

--}

data Deque a = Nil | Singleton a | Deque a a [a]
  deriving (Show)

-- remember: instance Traversable Deque (and supporting instances)

last  :: Deque a -> a
last deck =
  case deck of
    Nil -> error "Deque.last"
    Singleton x -> x
    Deque _ x _ -> x
first :: Deque a -> a
first deck =
  case deck of
    Nil -> error "Deque.first"
    Singleton x -> x
    Deque x _ _ -> x

(|<) :: Deque a -> a -> Deque a -- or 'postpend'
deck |< x =
  case deck of
    Nil -> Singleton x
    Singleton a -> Deque a x []
    Deque hd lst xs -> Deque hd x (xs ++ [lst])

(>|) :: a -> Deque a -> Deque a -- or 'prepend'
x >| deck =
  case deck of
    Nil -> Singleton x
    Singleton a -> Deque x a []
    Deque hd lst xs -> Deque x lst (hd:xs)

dequeFromList :: [a] -> Deque a
dequeFromList = foldr (>|) Nil

-- bonus:

-- zweitletztes deck gives the penultimate element of a deque

zweitletztes :: Deque a -> Maybe a
zweitletztes deck =
  case deck of
    Nil -> Nothing
    Singleton _ -> Nothing
    Deque _ _ xs -> Just . Prelude.last $ xs

{-

An implementation of zweitletztes for [a] could be written:

zweitletztes :: [a] -> a
zweitletztes = last . init

-}

-- a verbose, hintful, version of this file is at http://lpaste.net/106730