11
\$\begingroup\$

I'm learning Haskell using the University of Pennsylvania's online materials. I'm a few lessons in and was looking for some feedback about whether I'm thinking functionally enough or porting over my Python background inappropriately.

Below are my answers to the problems set out in lesson three (these were someone's homework once but not any more, and were never mine!). Is my code below making any rookie mistakes for someone coming from another paradigm to functional?

import Data.List

-- Exercise 1
-- Take a list xs and an integer n, and return a list of every nth element of xs
everyNth :: [a] -> Int -> [a]
everyNth xs n = [snd x | x <- (zip [1..] xs), fst x `mod` n == 0]

skips :: [a] -> [[a]]
skips xs = map (everyNth xs) [1..length xs]

-- Exercise 2
-- Take a list of integers and produce a list of local maxima
triples :: [a] -> [[a]]
triples (x:xs)
  | length (x:xs) < 3 = []
  | otherwise = (x:take 2 xs) : triples xs

isMiddleMax :: (Ord a) => [a] -> Bool
isMiddleMax (x:y:z:[]) = x < y && y > z

localMaxima :: [Integer] -> [Integer]
localMaxima xs = map maximum . filter isMiddleMax $ triples xs

-- Exercise 3
-- Take a list of integers 0-9 and return a histogram
groupSort :: (Eq a, Ord a) => [a] -> [[a]]
groupSort xs = group $ sort xs

countInstance :: (Eq a, Ord a) => [a] -> (a, Int)
countInstance xs = (head xs, length xs)

countInstances :: (Eq a, Ord a) => [a] -> [(a, Int)]
countInstances xs = map (countInstance) $ groupSort xs

maxInstances :: [Int] -> Int
maxInstances xs = maximum $ map (snd) $ countInstances xs

spaceOrStar :: [Int] -> Int-> Char
spaceOrStar xs y
  | y `elem` xs = '*'
  | otherwise = ' '

getData :: (Eq a, Ord a) => [a] -> Int -> [a]
getData xs n = [fst x | x <- countInstances xs, snd x >= n]

histRow :: [Int] -> String
histRow xs = map (spaceOrStar xs) [0..9]

buildHist :: [Int] -> String
buildHist xs = intercalate "\n" . map (histRow) $ map (getData xs) . reverse $ [1..maxInstances xs]

histogram :: [Int] -> String
histogram xs = buildHist xs ++ "\n==========\n0123456789\n"

main :: IO()
main = do
    print $ skips "ABCD"
    print $ skips "hello!"
    print $ skips [1]
    print $ skips [True, False]
    print $ skips ([] :: [Int])
    print $ localMaxima [2,9,5,6,1]
    print $ localMaxima [2,3,4,1,5]
    print $ localMaxima [1,2,3,4,5]
    putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]
\$\endgroup\$
  • \$\begingroup\$ Note that code golfing (brevity for the sake of brevity) is off-topic for Code Review. However, we can assist with writing reasonably short implementations. \$\endgroup\$ – 200_success Jan 27 '15 at 23:22
15
\$\begingroup\$

Overall it's pretty nice. I like that you've learned how to use $; it really improves readability in my opinion. One thing that immediately caught my attention though was the chain of prints. Haskell can do better! You can for example put those in a list, and mapM_ print over it.

let fns = 
    [ skips "ABCD"
    , skips "hello!"
    , skips [1]
    , skips [True, False]
    , skips ([] :: [Int])
    , localMaxima [2,9,5,6,1]
    , localMaxima [2,3,4,1,5]
    , localMaxima [1,2,3,4,5]
    ]

mapM_ print fns

This makes it easier to refactor later, if you want to do something else than print, write them to different files, all kinds of stuff. The lisp-ish approach of code-as-data is quite useful when enumerating cases like you did here.


isMiddleMax (x:y:z:[]) = x < y && y > z

Spooky! Use -Wall to get a proper warning for that one: incomplete patterns in function .... You might want to consider adding a meaningful error message:

isMiddleMax _ = error "Only works on 3-element lists!"

triples (x:xs)
  | length (x:xs) < 3 = []

Dunno if you know, but there exists a thing called "alternate name capture"; it's written like so:

triples (x:xs @ allXs)
  | length allXs < 3 = []

If you consider this an overkill, why not simply change the clause to length xs < 2? I don't like the same pattern repeated for some reason.


countInstances xs = map (countInstance) $ groupSort xs

maxInstances xs = maximum $ map (snd) $ countInstances xs

The parens around countInstance and snd are unnecessary (it's not terrible to leave them, just pointing that out). HLint is a useful tool that can provide such hints for you!


Oh, and also, in the second case; multiple $ are a bit less readable; consider this instead:

maxInstances xs = maximum . map (snd) . countInstances $ xs

This expresses it in a truly functional way, and makes it susceptible to eta-reduction!:

maxInstances = maximum . map (snd) . countInstances

This is called point-free (not to be confused with pointless :)) notation, and makes it extremely clear that the function is indeed a composition of other functions ((.) is Haskell's composition operator).


I'll add more if I notice any more areas for improvement.

\$\endgroup\$
7
\$\begingroup\$

I'm surprised nobody mentioned the thing that stood out to me the most: the definition of triples:

triples :: [a] -> [[a]]
triples (x:xs)
  | length (x:xs) < 3 = []
  | otherwise = (x:take 2 xs) : triples xs

This is tremendously inefficient: an O(N2) algorithm instead of O(N) just because of the repeated calls to length. Instead, you should just use pattern matching:

triples :: [a] -> [[a]]
triples (x:y:z:xs) = [x,y,z] : triples (y:z:xs)
triples _ = []

You can additionally use an as-pattern to avoid re-building the list (y:z:xs):

triples :: [a] -> [[a]]
triples (x:more@(y:z:xs)) = [x,y,z] : triples more
triples _ = []

Relatedly, another of the answers pointed out the inexhaustive pattern match in isMiddleMax: it only works for lists of length exactly 3. A workaround was proposed, but the real answer is: use a 3-tuple instead of a list! This means changing the type of triples to [a] -> [(a,a,a)], and then isMiddleMax is super easy to write. You need a small change to localMaxima as well, to consume the new type:

triples :: [a] -> [(a,a,a)]
triples (x:more@(y:z:xs)) = (x,y,z) : triples more
triples _ = []

isMiddleMax :: Ord a => (a,a,a) -> Bool
isMiddleMax (x,y,z) = y > x && y > z

localMaxima :: [Integer] -> [Integer]
localMaxima xs = map middle . filter isMiddleMax $ triples xs
  where middle (x,y,z) = y
\$\endgroup\$
3
\$\begingroup\$

Definitely a good start, what's left to improve will come with familiarity and practice. Here are a couple of iterative improvements you might make to everyNth that show where your mental model might differ from a more experienced Haskeller's.

The parentheses around zip are unnecessary. As are, e.g., the parentheses around snd in an argument to map in your definition of maxInstances. Excess parentheses while syntactically harmless are gratuitous line noise, and common Haskell style strongly favors concision and cleanliness.

everyNth xs n = [snd x | x <- zip [1..] xs, fst x `mod` n == 0]

Notice that you use both fst x and snd x in the same scope. Use pattern matching instead, instead of using x as an intermediary identifier you can directly expose the components of the tuple and probably give them names that help your code be self-documenting and thus clearer.

everyNth xs n = [x | (i, x) <- zip [1..] xs, i `mod` n == 0]

Performing math on indices definitely implies an imperative-programmer mindset to me. Instead of indices, use the value you really care about! In this case, pair each x value with a Boolean that indicates whether it should be included in the output. This is easy to do because the pattern of inclusions are a simply repeating cycle.

everyNth xs n = [x | (include, x) <- zip (cycle includes) xs, include]
    where includes = [i `mod` n == 0 | i <- [1..n]]

The above version is contrived to (hopefully) show just what went where without piling on too many changes at once. This version introduces cycle :: [a] -> [a], which creates an infinite list out of a finite one by repeatedly appending the list to itself (in effect). We restrict the range of our indices to [1..n] because we know they're completely predictable and periodic after that range. To take it a step further we can directly pattern match on the value of include :: Bool in our tuple. This usually is non-obvious to beginners and so is worth showing on its own.

everyNth xs n = [x | (True, x) <- zip (cycle includes) xs]
    where includes = [i `mod` n == 0 | i <- [1..n]]

Notice that we've eliminated the predicates from our first list comprehension! I'll get back to that in a bit. Our next step is to lose the contrivance from the definition of includes, this bit of functionality would obviously be better expressed by mapping over the range instead of using a list comprehension (again I only did so to minimize the changes between steps).

everyNth xs n = [x | (True, x) <- zip (cycle includes) xs]
    where includes = map (\i -> i `mod` n == 0) [1..n]

Performing any modulus operations at all is unnecessary though, it's obvious that in the range [1..n] only the final element will satisfy the modulus operation. Instead we can directly build the list of booleans from what we know about the length of the period.

everyNth xs n = [x | (True, x) <- zip (cycle includes) xs]
    where includes = replicate (n - 1) False ++ [True]

This is probably as far as I would take it having started out at your original version. There aren't any real further improvements that I can see, just matters of personal style. If I were to write this from scratch though I'd probably produce something that looked more like this.

everyNth :: Int -> [a] -> [a]
everyNth n = map snd . filter fst . zip (cycle (replicate (n-1) False ++ [True]))

Or if I was feeling particularly flashy, I'd write this, and then spend 30 minutes arguing myself out of it for being hopelessly overwrought.

import Data.Maybe (catMaybes)

everyNth :: Int -> [a] -> [a]
everyNth n = catMaybes . zipWith (\b x -> if b then Just x else Nothing)
                                 (cycle (replicate (n-1) False ++ [True]))
\$\endgroup\$
  • \$\begingroup\$ \b x in your last example looks like it could be wrapped too. \$\endgroup\$ – Bartek Banachewicz Jan 28 '15 at 8:40
  • \$\begingroup\$ Wrapped? Not sure I know what you mean. I tried as hard as I could to think of a clever combination of Prelude functions that could replace that lambda, but my imagination failed me. \$\endgroup\$ – bisserlis Jan 28 '15 at 8:47
  • \$\begingroup\$ Oh in something ad-hoc, just to move the lambda out of the main expression; it's broken up into two lines anyway. Also, just for the fun of it: \b -> if b then Just else const Nothing :) \$\endgroup\$ – Bartek Banachewicz Jan 28 '15 at 8:51
  • \$\begingroup\$ Gotcha. Maybe when :: Bool -> a -> Maybe a. I frequently want zipWithMaybe :: (a -> b -> Maybe c) -> [a] -> [b] -> [c] which then allows everyNth n = zipWithMaybe when multipleOfN where multipleOfN = cycle (replicate (n-1) False ++ [True]) which is pretty cool. \$\endgroup\$ – bisserlis Jan 28 '15 at 9:13
0
\$\begingroup\$

Just for fun, these are my implementations:

Edit: These implementations take advantage of recursive function definitions. I think the ease of writing recursive functions is one of Haskell's many great features, so I thought I would show it off a little. It's part of "thinking functionally", and I think you should use it more often.

-- Exercise 1: Skips
skip :: Int -> [a] -> [a]
skip n x
    | length x >= n = last (take n x) : skip n (drop n x)
    | otherwise     = []

skips :: [a] -> [[a]]
skips x = map ((flip skip) x) [1..length x]

A minor difference here is that I implemented skip (everyNth in your solution) as (Int -> [a] -> [a]), since I think (skip n) is more adaptable to other contexts than (skip x) with partial function application.

Just for demonstration purposes, could also implement skips recursively. Here's an implementation of map:

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

So, instead of using map in skips:

skipsR :: [a] -> [[a]]
skipsR x = skipsR' [1..length x]
  where
    skipsR' []     = []
    skipsR' (n:ns) = skip n x : skipsR' ns

Here's a recursive implementation of localMaxima:

-- Exercise 2: Local Maxima
localMaxima :: [Integer] -> [Integer]
localMaxima []       = []
localMaxima (_:[])   = []
localMaxima (_:_:[]) = []
localMaxima (x0:x1:xs)
    | x1 > x0 && x1 > head xs = x1 : localMaxima (x1:xs)
    | otherwise               = localMaxima (x1:xs)

You were really close to this one with your isMiddleMax function. Going a little further from there, we can use Haskell's pattern matching system to adapt the same function to any size of list. The resulting code has a lot fewer lines, and I suspect runs a little faster. Personally, I find recursive definitions to be more readable in many cases than mapping and filtering (pipeline approach), but that's just a preference.

For the histogram, I iterate over the list 10 times to count the number of occurrences of {0..9}, which is O(n). I then make a row of stars for each number in {1..maximum (counts)}, which is also O(n). I'll get back to you with a performance comparison with your code later.

-- Exercise 3: Histogram
count :: Integer -> [Integer] -> Int
count _ [] = 0
count n (x:xs)
    | x == n    = 1 + count n xs
    | otherwise = count n xs

This one recursively counts the number of occurrences of Integer n.

counts :: (Integer, Integer) -> [Integer] -> [Int]
counts (min, max) x = map ((flip count) x) [min..max] 

This one returns a list of counts for integers in {min..max}.

Again, we can unroll this into a recursive definition:

countsR :: (Integer, Integer) -> [Integer] -> [Int]
countsR (min, max) x = countsR' [min..max]
  where
    countsR' []     = []
    countsR' (n:ns) = count n x : countsR' ns

The idea of starString is to turn counts (0, 9) x into a row of stars. If starString gets and empty list, we can assume that we've reached the end of the line, and can add a newline character.

starString :: [Int] -> Int -> String
starString []     n = "\n"
starString (x:xs) n
    | x >= n    = '*' : starString xs n
    | otherwise = ' ' : starString xs n

This is equivalent to:

starString' xs n = map (star n) x ++ "\n"
  where 
    star n x | x >= n    = '*'
             | otherwise = ' '

You could do it either way. The map might actually be faster, but I haven't checked.

Finally:

histogram :: [Integer] -> String
histogram x = (map (starString cs) $ reverse [1..maximum cs])
              ++ "==========\n0123456789\n"
  where
    cs = counts (0, 9) x

The reverse ensures that the histogram isn't displayed upside down. You could apply it to (map (starString cs) [1..maximum cs]), but I reasoned that a list of integers is easier to reverse than a list of strings. I haven't checked though. I leave it as an exercise for you to unspool histogram into histogramR.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.