3
\$\begingroup\$

I am working through UPenn CIS 194: Introduction to Haskell (Spring 2013). Since I am not able to take the course for real I am asking for CR (feedback) as it could be from teacher in that course.

HW3 - Code golf - Full description

module Golf where

import Data.List

-- ["apple","orange","plum"] example
-- ... [("apple",0),("orange",1),("plum",2)] added indexes
-- ... [("apple",0),("orange",1),("plum",2)] filtered by predicate: index `mod` 1 == 0
-- [["apple","orange","plum"]] ++ ... [("orange",0),("plum",1)] added indexes
-- [["apple","orange","plum"]] ++ ... [("orange",0)] filtered by predicate: index `mod` 2 == 0
-- [["apple","orange","plum"]] ++ [["orange"]] ++ ... [[("plum",0)]] added index
-- [["apple","orange","plum"]] ++ [["orange"]] ++ ... [[("plum",0)]] filtered by predicate: 0 `mod` 3 == 0 
-- [["apple","orange","plum"]] ++ [["orange"]] ++ [["plum"]]
-- [["apple","orange","plum"],["orange"],["plum"]]
skips :: [a] -> [[a]]
skips = skips' 1

skips' :: Integer -> [a] -> [[a]]
skips' _ [] = []
skips' n root@(_:xs) = [fst $ unzip $ filter devidedByIndex $ zip root [0..]] ++ skips' (n + 1) xs
  where
    devidedByIndex x = (snd x) `mod` n == 0

-- [1,2,9,3]
-- 2 > 1 && 2 > 9 = False
-- localMaxima [2,9,3]
-- 9 > 2 && 9 > 3 = [9] ++ localMaxima [3]
-- [9] ++ []
-- [9]
localMaxima :: [Integer] -> [Integer]
localMaxima [] = []
localMaxima (x:[]) = []
localMaxima (x:y:[]) = []
localMaxima (x:y:z:xz)
  | y > x && y > z = [y] ++ localMaxima (z:xz)
  | otherwise      = localMaxima (y:z:xz)

-- putStr (histogram [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,7,7,7,8,8,9])
--      *
--     ***
--    *****
--   *******
--  *********
-- ==========
-- 0123456789
histogram :: [Integer] -> String
histogram m = transform (maximum n) n
  where
    n = countElements m

transform :: Int -> [Int] -> String
transform 0 _  = "==========\n0123456789\n"
transform i n  = intercalate "" ((map transform' n) ++ ["\n"]) ++ transform (i - 1) n
  where
    transform' x
      | x >= i    = "*"
      | otherwise = " "

-- count how many times each number appears in array
countElements :: [Integer] -> [Int]
countElements n = map count [0..9]
  where
    count x = length (elemIndices x n)
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that hard-core code golfing, where everything is sacrificed for reducing character count, is off-topic for Code Review. However, reasonable requests for conciseness are allowable. \$\endgroup\$ – 200_success Sep 21 '15 at 8:54
3
\$\begingroup\$

go

First just a blanket statement about names. Since this is a golfing challenge you should pick short names for varibles, helper functions, etc. Of course, that makes things less readable, but there are some conventions that Haskellers follow:

go         - names a local helper function
xs, ys, zs - a list
(x:xs)     - xs is the tail of a list whose head is x
x'         - a value related to x

Some people complain about the heavy use of single letter variable names in Haskell, but when used judiciously I think it actually aids readability.

skips

You can perform filter, fst and unzip all in a single list comprehension like this:

skips' n root@(_:xs) = [ x | (x,k) <- zip root [0..], mod k n == 0] ++ ...

Also, note that you define devidedByIndex, but you only call it once. In a situation like that you can always inline the definition where it is used, and that's what we've done here by putting the mod k n ... expression directly into the list comprehension.

localMaximum

You have three cases which return the same value, so just put the last case first and use a default pattern for the others:

localMaxima (x:y:z:xz) = ...
localMaximum _ = []

Next, because we're golfing, you can avoid the otherwise clause and duplicating the recursion call like this:

localMaxima (x:y:z:zs) = (if x < y && y > z then [y] else []) ++ localMaximum ...

histogram

There are two sub-problems:

  1. Computing the counts
  2. Building the picture.

Let's start with #2, and say we have the counts in a list ns, i.e. the counts for the example is [0,1,2,3,4,5,4,3,2].

A quick way to create the row for the k-th level is:

row k ns = [ if n >= k then '*' else ' ' | n <- ns ]

and then we just need to stack those lines together:

(row 9 ns) ++ "\n" ++ (row 8 ns) ++ "\n" ++ ... (row 1 ns) ++ "\n"

Perhaps this gives you some ideas on how to improve the code.

In your computeElements, again note that your helper count is only used once, so for golfing purposes you can inline it:

countElements n = map (\x -> length (elemIndices x n)) [0..9]

Also, compare:

elementIndices x n          - 16 non-space chars
[ y | y <- n, y == x ]      - 13 non-space chars

Since you only interested in the length both will work.

Finally, whenever you have map (\x -> ...) [...] it's the same as a list comprehension:

map (\x -> .A.) [.B.]  = [ .A. | x <- [.B.]]

and the list comprehension is shorter by a few characters.

import ...

The exercise encourages you to look for standard library functions to help you reduce your code size.

Here are some library functions which might be applicable to these problems:

tails :: [a] -> [[a]]
sort :: Ord a => [a] -> [a]
group :: Eq a => [a] -> [[a]]
unlines :: [String] -> String
\$\endgroup\$
  • \$\begingroup\$ skips' n root@(_:xs) = [ x | (x,k) <- zip root [0..], mod k n == 0]: list comprehension should be additionally wrapped by []. \$\endgroup\$ – drets Sep 20 '15 at 23:42
  • \$\begingroup\$ because I forgot the ... ++ skips' (n+1) xs part \$\endgroup\$ – ErikR Sep 20 '15 at 23:43
  • \$\begingroup\$ Updated version of code is available in the public gist file \$\endgroup\$ – drets Sep 21 '15 at 0:38
  • 1
    \$\begingroup\$ Yes - but unlines and unwords are good to know about. Also, you are notw set up to write histogram in the form unwords $ map ... which will allow you to make more reductions. \$\endgroup\$ – ErikR Sep 21 '15 at 15:24
  • 2
    \$\begingroup\$ Sorry - that should be unlines $ map ... \$\endgroup\$ – ErikR Sep 21 '15 at 18:50

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.