# Re-implementing basic list operations

I'm re-implementing the common core functions that work on list as a learning exercise. I'm new to Haskell and often find myself staring at what I've written trying to determine the simpler or more elegant solution I'm certain exists. I'm also unsure about my naming conventions, since there are some things the style guides I've read don't really cover. I'd appreciate any advice or criticism.

## foldl

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f accumulator [] = accumulator
foldl' f accumulator (x:xs) =
seq accumulator' \$ foldl' f accumulator' xs
where accumulator' = f accumulator x


I wrote this for the ListOps https://exercism.io challenge, which had a requirement about strictness.

## foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f accumulator []     = accumulator
foldr f accumulator (x:xs) = f x (foldr f accumulator xs)


## length

length :: [a] -> Int  -- Deliberately not using a fold
length = length' 0

length' :: Int -> [a] -> Int
length' accumulator [x]    = 1
length' accumulator (x:xs) = 1 + length' accumulator xs
length' accumulator []


## map

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f [x]    = [f x]
map f (x:xs) = f x:map f xs


## filter

filter :: (a -> Bool) -> [a] -> [a]
filter _ []    = []
filter f (x:xs)
| f x         = x : filter f xs
| otherwise   = filter f xs


## (++)

(++) :: [a] -> [a] -> [a]
xs ++ [] = xs
xs ++ ys = foldr (:) ys xs


# foldl'

Your implementation is fine, but generally, seq is written infix, like a seq b. Therefore, I’d write it like this:

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f accumulator [] = accumulator
foldl' f accumulator (x:xs) =
accumulator' seq foldl' f accumulator' xs
where accumulator' = f accumulator x


I’ve also indented the second to last line to visually distinguish it more from the where clause.

# foldr

Your implementation looks good to me.

# length

You mention that you’re explicitly avoiding fold, but why? There’s no reason to avoid it here. Still, even without using it, your implementation can be improved.

Usually, helper functions like length' are nested inside a where clause, sometimes idiomatically named go. Additionally, your 1-element case is unnecessary, since (x:xs) will match a 1-element list. Finally, your use of an accumulator is pointless, since you never actually change it from 0, and your function isn’t tail recursive. Therefore, I would write length like this if you really want to avoid a fold:

length :: [a] -> Int
length = go 0
where go accumulator [] = accumulator
go accumulator (x:xs) = go (accumulator + 1) xs


This actually uses the accumulator, which allows it to be tail recursive.

# map

Again, I would use a fold here. An implementation with foldr would look like this:

map :: (a -> b) -> [a] -> [b]
map f = foldr (\x xs -> f x : xs) []


However, if you want to write the recursion manually, your 1-element case is once again redundant. You could simplify your implementation to this:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs


# filter

Once again, I would use a fold here:

filter :: (a -> Bool) -> [a] -> [a]
filter f = foldr (\x xs -> if f x then x : xs else xs) []


If you want to use explicit recursion, though, your implementation looks fine.

# (++)

Your 0-element case is redundant here because foldr will handle the 0-element case just fine on its own. You can eliminate it entirely:

(++) :: [a] -> [a] -> [a]
xs ++ ys = foldr (:) ys xs

• Thanks for these tips, appreciate them. Especially about tail recursion on length, and pointing out that x:xs matches a 1-element list, which I assumed (never assume) it wouldn't based on other languages I've used. Big help. (And I was only avoiding fold as a challenge to myself.) Jan 8, 2017 at 15:32
• @RyanPlant The reason x:xs matches a 1 element list is that the [] type is effectively defined as if it were data [a] = [] | a : [a], were that valid syntax. Without the special syntax, you can think of it as being defined like data List a = Nil | a : List a. Since the right hand side of (:) is a List a, and Nil is a valid List a, then a single-element list will match the x:xs pattern, where x will be the single element and xs is Nil / []. Haskell lists are just ordinary ADTs, just with some special syntax built into the language. Jan 8, 2017 at 20:18