UPenn Homework 3: skips function

Question

I've started learning Haskell by following along the CIS 194 Course from UPenn. In the first lessons there is talk about wholemeal programming and certain ways idiomatic Haskell code looks like. Now, I think that my style is still far away from being idiomatic and I don't think I've grasped what wholemeal means. To see how far away, I'd like some comments on code from the third assignment because that's where I struggled most (until now).

So, how far away from being idiomatic is the code? How's efficiency?

Exercise 1: skips :: [a] -> [[a]]

The n^th list in the output should contain every n^th element from the input list. For example, skips "hello!" == ["hello!", "el!", "l!", "l", "o", "!"].

skips :: [a] -> [[a]]
skips list =
  let pos 1 l = l
      pos i lst =
        let tmp = drop (i-1) lst
        in case tmp of
            [] -> []
            x:xs -> x : (pos i xs)
      tmpSkps i acc lst = if i == (length lst)+1
                          then acc
                          else tmpSkps (i+1) ((pos i lst):acc) lst
  in reverse (tmpSkps 1 [] list)

Answer 1

In Haskell, you want to avoid thinking in a sequential, step-by-step-in-a-specific-order sort of way, whenever possible. You want to try to write an expression or function that means what you want to do, rather than trying to tell the computer exactly what steps to perform at what time. Also, think of function calls as the values they return, not as an action to be performed.

Most of your code is step-by-step recursive stuff, and not very idiomatic. Not all recursion is non-idiomatic in Haskell, but it is if the recursion can be replaced by library functions like map, filter, and fold.

tmpSkps keeps track of an index as it recurses, a more idiomatic way to keep track of an index (if you need to) would be to use zip [1..] xs. But the entire tmpSkps function can be replaced with a call to map. map f [1..n] will make a list [f 1, f 2, f 3, ... f n].

In several places, you use list or lst for a list; idiomatic Haskell would use xs or ys.

pos is a bad name, I'd replace it with something more descriptive, like keepNth. It wouldn't be the most efficient thing in the world, but there's a fairly straightforward way of writing pos with zip, filter, and map, along with a lambda expression that checks whether a number is divisible by n.

Answer 2

The Lecture Notes advocate "wholemeal" programming, which I would summarize as being the use of higher-order functions. Your code, on the other hand, suffers from the "indexitis" that you are being encouraged to avoid.

The key insight for this exercise is that it resembles a list-chunking problem. If you transform "hello!" into, say, chunks of increasing length…

[
    ["h", "e", "l", "l", "o", "!"],
    ["he", "ll", "o!"],
    ["hel", "lo!"],
    ["hell"],
    ["hello"],
    ["hello!"]
]

… then the problem boils down to taking the last element of each substring.

skips :: [a] -> [[a]]
skips xs =
  map (map last . fullChunks) $ zip [1..] (replicate (length xs) xs)
  where
    fullChunks (n, ys)
      | n > length ys = []     -- Discard incomplete chunks
      | otherwise     = chunk : fullChunks (n, rest)
      where (chunk, rest) = splitAt n ys

Unfortunately, you can't use the functions provided by Data.List.Split, since incomplete chunks at the end need to be discarded.

Answer 3

In the lecture notes, a recursive implementation of a function is criticised because, "it is doing too much at once; and working at too low of a level". That could also be said of your solution.

One alternative might be to implement a function everyNth, which returns every nth element of its input. Then you could do something like,

skips xs = map (\n -> everyNth n xs) [1..length xs]