Haskell's missing core type classes

List.hs

module MissingTypeClassesIntegration.List where

import MissingTypeClasses
import Prelude hiding (foldl, foldl1, foldr, foldr1, map, filter, zip)

instance RecursiveDataStructure [] where
    unit = []
    cons = (:)

instance LeftFoldable [] where
    foldl _ y [] = y
    foldl f y (x:xs) = foldl f (f y x) xs

    foldl1 _ [] = error "empty list"
    foldl1 f (x:xs) = foldl f x xs

instance RightFoldable [] where
    foldr _ y [] = y
    foldr f y (x:xs) = f x (foldr f y xs)

    foldr1 _ [] = error "empty list"
    foldr1 f xs = foldr f (last xs) (init xs)

instance Mappable [] where
instance Filterable [] where
instance Partitionable [] where

MissingTypeClasses.hs

module MissingTypeClasses where

import Prelude hiding (foldl, foldl1, foldr, foldr1, map, filter, zip, zipWith)

class RecursiveDataStructure rds where
    unit :: rds x
    cons :: x -> rds x -> rds x

class RecursiveDataStructure f => LeftFoldable f where
    foldl  :: (y -> x -> y) -> y -> f x -> y
    foldl1 :: (x -> x -> x) -> f x -> x

class RecursiveDataStructure f => RightFoldable f where
    foldr  :: (x -> y -> y) -> y -> f x -> y
    foldr1 :: (x -> x -> x) -> f x -> x

class RightFoldable m => Mappable m where
    map :: (x -> y) -> m x -> m y
    map f xs = foldr (cons . f) unit xs

class RightFoldable f => Filterable f where
    filter :: (x -> Bool) -> f x -> f x
    filter f xs = foldr matcher unit xs
        where matcher x xs'
                | f x       = cons x xs'
                | otherwise = xs'

class RightFoldable p => Partitionable p where
    partition :: (x -> Bool) -> p x -> (p x, p x)
    partition f xs = foldr partitioner (unit, unit) xs
        where
            partitioner x (ts, fs)
                | f x       = (cons x ts, fs)
                | otherwise = (ts, cons x fs)

class RightFoldable z => Zippable z where
    zipWith :: (a -> b -> c) -> z a -> z b -> z c
    zip :: z a -> z b -> z (a, b)

    zip = zipWith (,)

playground.hs

module Main where

import MissingTypeClasses
import MissingTypeClassesIntegration.Array
import MissingTypeClassesIntegration.Tree

import Prelude hiding (foldl, foldl1, foldr, foldr1, map, filter, zip, zipWith)
import qualified Prelude (foldl, foldl1, foldr, foldr1, map, filter, zip, zipWith)
import Data.Maybe (listToMaybe)
import Data.List (sort, group)

instance Zippable [] where
    zipWith f xs ys = foldr step (const []) xs ys
        where
            step x zipsfn []     = []
            step x zipsfn (y:ys) = f x y : (zipsfn ys)

main :: IO ()
main = print $ zip [1..3] [2..4]

Tree.hs

module MissingTypeClassesIntegration.Tree where

import Data.Tree
import MissingTypeClasses
import MissingTypeClassesIntegration.Array
import Prelude hiding (foldl, foldl1, foldr, foldr1, map, filter, zip)

instance RecursiveDataStructure Tree where
    unit = undefined
    cons x node = Node x [node]

instance RightFoldable Tree where
    foldr f y node = foldr f y (flatten node)
    foldr1 f (Node x subForest) = foldr f x (concatMap flatten subForest)

instance Filterable Tree