7
\$\begingroup\$

I am following CIS 194: Introduction to Haskell (Spring 2013) online to teach myself Haskell. Following is my response to third exercise of Homework 3, namely Histogram.

In which ways I could improve this, without getting too much into advanced topics of Haskell?

{-
For this task, write a function
histogram :: [Integer] -> String
which takes as input a list of Integers between 0 and 9 (inclusive),
and outputs a vertical histogram showing how many of each number
were in the input list. You may assume that the input list does not
contain any numbers less than zero or greater than 9 (that is, it does
not matter what your function does if the input does contain such
numbers). Your output must exactly match the output shown in the
examples below.

-}
histogram :: [Integer] -> String
histogram numbers =
    let initialcounts = take 10 (repeat 0)
        calculatedcounts = histogramcount numbers initialcounts
        maxheight = maximum calculatedcounts
        linefunctions = map drawline [maxheight,maxheight-1..1]
    in unlines ((map ($ calculatedcounts) linefunctions) ++ ["==========","0123456789"])

histogramcount :: [Integer] -> [Int] -> [Int]
histogramcount [] counts = counts
histogramcount (x:xs) counts =
    let
        xint = fromIntegral x
        newcount = (counts !! xint) + 1
    in histogramcount xs (take xint counts ++ [newcount] ++ drop (xint+1) counts)

drawline :: Int -> [Int] -> String
drawline level = map (\x -> if x >= level then '*' else ' ')

main = do
    putStr $ histogram [1,1,1,5]
    putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]
\$\endgroup\$
3
\$\begingroup\$

See below for comments on your overall approach, but taking the approach as a given, here are a few observations:

First, it seems unusual to pass initialcounts to histogramcount instead of making histogramcount self-contained. Also, histogramcount is kind of a long name for such a simple function, and take 10 (repeat 0) is more succinctly written replicate 10 0. Finally, the complex step of actually incrementing the count seems like it deserves its own function, so I might write:

-- |Return counts of integers from 0 to 9
count :: [Integer] -> [Int]
count = loop (replicate 10 0)
  where loop counts (x:xs) = loop (increment x counts) xs
        loop counts []     = counts

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  let xint = fromIntegral x
      newcount = (counts !! xint) + 1
  in  take xint counts ++ [newcount] ++ drop (xint+1) counts

There's no particular reason to name linefunctions, and if you write:

map ($ calculatedcounts) (map drawline [maxheight,maxheight-1..1])

a pair of maps like this simplifies to a single map:

map (\height -> drawline height calculatedcounts) [maxheigh,maxheight-1..1]

which might be more clearly written as a list comprehension anyway:

[drawline h calculatedcounts | h <- [maxheight,maxheight-1..1]]

giving:

histogram :: [Integer] -> String
histogram numbers =
  unlines $ [drawline h counts | h <- [maxh,maxh-1..1]] ++ footer
  where counts = count numbers
        maxh = maximum counts
        footer = ["==========","0123456789"]

Note that Haskell code usually uses pretty short names for temporary variables. It's also more common to use a where clause rather than a let clause when the variables being defined are just helpers, secondary to the main expression. (Here, counts is arguable not secondary to the main expression, though that raises the question of whether or not we should separate out the function that graphs a set of 10 counts instead of combining it with the counting itself... hmm...)

The drawline function seems okay. Again, maybe a list comprehension is clearer:

drawline :: Int -> [Int] -> String
drawline level counts = [if x >= level then '*' else ' ' | x <- counts]

or maybe you want to go the route of being excessively clever:

drawline :: Int -> [Int] -> String
drawline level = map (bool ' ' '*' . (>= level))

Before doing that, we should revisit increment. It's pretty terrible. The take/drop pair can be replaced with the more efficient splitAt standard function which can simultaneously fetch the current count and get everything prepared to update the count, like so:

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  case splitAt (fromIntegral x) counts of
    (a,n:b) -> a ++ (n+1):b

That's better, and fairly idiomatic. Note the use of a ++ (n+1):b in place of a ++ [n+1] ++ b, too. That's pretty standard.

After you complete next week's lesson, you may discover that count is a fold and rewrite it as:

count :: [Integer] -> [Int]
count = foldr increment (replicate 10 0)

Further down the line, you may become concerned about whether a left fold would have been better for efficiency purposes, but there's not much point in worrying about that now.

Putting it all together, including breaking histogram up into the counting and the plotting and pulling the drawline helper function into the plot function, I might rewrite your program as:

-- |Plot histogram of counts
histogram :: [Integer] -> String
histogram = plot . count

-- |Return counts of integers from 0 to 9
count :: [Integer] -> [Int]
count = foldl (flip increment) (replicate 10 0)

-- |Add one to a given count
increment :: Integer -> [Int] -> [Int]
increment x counts =
  case splitAt (fromIntegral x) counts of
    (a,n:b) -> a ++ (n+1):b

-- |Plot a vertical bar chart of counts
plot :: [Int] -> String
plot counts =
  unlines $ [drawline h | h <- [maxh,maxh-1..1]] ++ footer
  where drawline level = [if x >= level then '*' else ' ' | x <- counts]
        maxh = maximum counts
        footer = ["==========","0123456789"]

main = do
  putStr $ histogram [1,1,1,5]
  putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]

Finally, I'd run hlint on it. It gives "No hints", but if I'd run it earlier, it would have mentioned replicate 10 0 and recommended a foldl for the count version that used recursive loop calls.

Is this better than your original? Well, I think so, of course, or I wouldn't be writing this. I think the main improvements are:

  • removing long names for things that aren't very important, like linefunctions or initialcounts
  • giving top-level names to self-contained actions like count, increment, and plot that perform more well-defined operations than your original "histogramcount" and "drawline"

Now, let's get back to your overall approach. The main criticism I have is that, like many new Haskell programmers, you're still trying to get over the tendency to use Haskell as an alternate syntax for writing Python (or any other imperative programming language of your choice). You've started with an array of counts:

counts = [0] * 10    # Python syntax!

and you've looped over the input data, updating each count as you go:

for c in data:
    counts[c] += 1

Unfortunately, Haskell isn't Python, so you've had to represent your running counts as a list. It has to be passed around as an extra argument, and it not only provides inefficient O(n) access to individual elements but also requires creating an updated immutable copy for every processed data point using the abominable expression:

take xint counts ++ [newcount] ++ drop (xint+1) counts

or its equally hideous cousin:

case splitAt (fromIntegral x) counts of (a,n:b) -> a ++ (n+1):b

Now, one "improvement" would be to switch from inefficient lists to an efficient Vector type to hold your counts. Honestly, though, the resulting program would still be designed around your original imperative solution, and we aren't seriously concerned with efficiency here anyway. If we need to process a few million data points, the fact that counting is slow isn't really the biggest issue as we try to generate hundreds of thousands of lines of vertical histogram output.

Instead, to really get a feeling for how Haskell programming is supposed to work, I'd suggest that you take a careful look at Data.List and try to imagine using the functions there as a pipeline of transformations on your data that gradual convert it from [Integer] to String. See if you can do it without keeping track of any intermediate state, like counts or the current line "level" or anything like that. As a hint, note that if you were to sort your data and then group it, you'd be close to having a set of required counts.

SPOILERS

Here's a super Haskelly solution to this problem. Note how its just a pipeline of functional transformations composed together. Read the pipeline from the bottom-up to understand how it works:

haskellHistogram :: [Integer] -> String
haskellHistogram =
    unlines      -- and print it as lines
  . reverse      -- flip it upside down
  . (['0'..'9']:) . (replicate 10 '-':)  -- add the header rows
  . takeWhile (any (=='*'))  -- take rows until we run out of stars
  . transpose    -- switch from horizontal rows of stars to vertical columns
  . map (  (++ repeat ' ')       -- extend with (infinite) spaces
         . flip replicate '*'    -- represent count as stars
         . (subtract 1)          -- drop the extra number we added
         . length                -- get the count
        )        -- for each group
  . group        -- group into 0s, 1s, 2s, etc.
  . sort         -- sort the input
  . ([0..9]++)   -- add one of each to ensure non-zero counts

I wrote that in one go, starting at the end of the pipeline and working my way backward, in about 5 minutes. After it type checked and I tested it, I found I'd forgotten the unlines (because my type signature was wrong!) and the subtract 1, but it otherwise worked correctly. That's what makes Haskell programming so much fun.

| improve this answer | |
\$\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.