Skip to content

Instantly share code, notes, and snippets.

@nicola-gigante
Created November 18, 2014 15:21
Show Gist options
  • Save nicola-gigante/43533ce907f88a6aba16 to your computer and use it in GitHub Desktop.
Save nicola-gigante/43533ce907f88a6aba16 to your computer and use it in GitHub Desktop.
A list-like datatype implemented with function composition to have constant-time appending. All the operations seems to preserve the original lazyness properties. Is there something wrong with this code?
{-# LANGUAGE TypeFamilies #-}
module List (
List,
fromList,
toList,
empty,
singleton,
head,
tail
) where
import Prelude hiding (empty, head, tail)
import qualified Prelude as P
import GHC.Exts (IsList, toList, fromList, Item)
import Data.Monoid (Monoid, mempty, mappend, mconcat)
import Data.Functor (Functor, fmap)
import Data.Foldable (Foldable, foldMap, foldr)
import Control.Applicative (Applicative, pure, (<*>))
import Control.Monad (Monad, return, (>>=))
-- Data type is just a function
newtype List a = List ([a] -> [a])
-- Conversion to and from plain lists
instance IsList (List a) where
type Item (List a) = a
fromList = List . mconcat . map (:)
toList (List f) = f []
--
-- List-like interface
--
empty :: List a
empty = List id
singleton :: a -> List a
singleton = List . (:)
head :: List a -> a
head = P.head . toList
tail :: List a -> List a
tail = fromList . P.tail . toList
-- Instances of common type classes
instance Eq a => Eq (List a) where
l1 == l2 = toList l1 == toList l2
l1 /= l2 = toList l1 /= toList l2
instance Ord a => Ord (List a) where
compare l1 l2 = compare (toList l1) (toList l2)
instance Functor List where
fmap f = fromList . fmap f . toList
instance Foldable List where
foldMap f = foldMap f . toList
instance Show a => Show (List a) where
showsPrec d = showsPrec d . toList
instance Monoid (List a) where
mempty = empty
mappend (List f1) (List f2) = List (f1 . f2)
instance Applicative List where
pure = List . (:)
f <*> a = fromList $ toList f <*> toList a
instance Monad List where
return = List . (:)
l >>= f = mconcat . toList $ fmap f l
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment