Created
November 18, 2014 15:21
-
-
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?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# 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