6
\$\begingroup\$

I am starting out in Haskell and thought I would try to make a function that got the index (nth) from the end of the list.

So getNthFromEnd 5 [1..10] would equal 5

The code I have so far is

getNthFromEnd :: Int -> [a] -> a
getNthFromEnd _ [] = error "Empty list given"
getNthFromEnd nth list
    | listLength < nth = error $ "List length must be greater than " ++ show nth
    | listLength == nth = head list
    | listLength >= nth = list !! (listLength - nth - 1)
    where listLength = length list
getNthFromEnd _ _ = error "Unknown exception occurred"

The code works as intended as far as I can tell, but seeing as though I am just getting to know Haskell I thought your suggestions on how this code could be cleaned up or refactored to make better use of FP concepts would be invaluable to my learning of Haskell and the FP paradigm overall.

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

I'll go through the code line-by-line:

 1    getNthFromEnd :: Int -> [a] -> a
 2    getNthFromEnd _ [] = error "Empty list given"
 3    getNthFromEnd nth list
 4        | listLength < nth = error $ "List length must be greater than " ++ show nth
 5        | listLength == nth = head list
 6        | listLength >= nth = list !! (listLength - nth - 1)
 7        where listLength = length list
 8    getNthFromEnd _ _ = error "Unknown exception occurred"

Line 1

Type signature - good!

Line 2

A function which calls out to error is kinda frowned upon. Such functions are called partial functions because they could throw an exception and that is not indicated in the type signature. That's why some people don't like to use head and tail - they prefer to use pattern matching instead for these functions. This is not really a critic of your code, more just an observation. If you were to write documentation for this function you might warn users that it is partial, although they might be able to guess from the description that it necessarily has to be.

More on partial functions:

https://begriffs.com/posts/2013-08-18-dont-be-partial-to-partial-functions.html

Line 4

I would change the error message to List length must be at least ... to match the comparison.

Lines 4 -- 6

Clearly one of the three comparisons has to hold, so for efficiency you can change the guard in line 6 to an otherwise clause:

| listLength < nth  = ...
| listLength == nth = ...
| otherwise         = ...

This avoids an unnecessary comparison check when listLength is greater or euqal to nth.

Another common Haskell idiom is to match on the result of compare like this:

-- may need Data.Ord

case compare listLength nth of
  LT  -> ...
  EQ  -> ...
  GT  -> ...

This has the advantage of being provably exhaustive by the compiler. However, it may turn out to be the slowest of the three. It depends a lot on how smart the compiler is. I don't see it used a lot in the Prelude functions for integer comparisons, and I imagine there is an efficiency reason behind that.

To summarize:

  • The code you've written is exhaustive (handles all the cases) just because we know that one of the comparisons has to hold. But GHC can't prove this, and it may perform an extra comparison when it doesn't need to.
  • Using an otherwise clause is exhaustive because we're using an otherwise clause. But it avoids an extra check sometimes.
  • Using compare is provably exhaustive by the compiler.

In any case, this declaration will handle all the cases which leads to...

Line 8

Based on the previous discussion, your function will never get to this point so this line isn't needed. Even if it did, GHC will throw it's own error with a message like:

*** Exception: /tmp/err.hs:3:1-17: Non-exhaustive patterns in function foo

Moreover, having this catch-all clause is hiding a potentially useful warning. If you remove that line and compile with -Wall GHC reports:

/tmp/pats.hs:5:1: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘getNthFromEnd’: Patterns not matched: _ (_ : _)

This raises two points:

  1. The way you've written the code you are not proving to GHC that you are handling all of the list patterns. GHC would like you to write the second stanza with a pattern:

    getNthFromEnd nth list@(:) =

That enables GHC to know that you've covered both the empty list and non-empty list cases.

  1. Using the catch-all clause prevents GHC from making this check.
\$\endgroup\$
1
  • \$\begingroup\$ Wow, thanks for such a comprehensive answer. I adjusted the function by adding the otherwise clause in place of the >= guard. I then removed the getNthFromEnd _ _ pattern (I think that is that is). I will look further into the partial functions 'situation' \$\endgroup\$ – Harry May 19 '16 at 19:25
3
\$\begingroup\$

@ErikR has already said a lot. I would like to add to his point about partial function. You can avoid throwing error by using Data.Maybe.

It would then look something like (just modifying your function):

getNthFromEnd :: Int -> [a] -> Maybe a
getNthFromEnd _ [] = Nothing
getNthFromEnd nth list
    | listLength < nth = Nothing
    | listLength == nth = Just (head list)
    | listLength >= nth = Just (list !! (listLength - nth - 1))
    where listLength = length list
getNthFromEnd _ _ = Nothing
\$\endgroup\$
0
\$\begingroup\$

Ignoring what kind of error messages you get, you don't need to handle error cases yourself: (!!) already does that.

getNthFromEnd :: Int -> [a] -> a
getNthFromEnd nth list = list !! (length list - nth - 1)

(Intermediately, you could also have left out the [] line.)

\$\endgroup\$
0
\$\begingroup\$

Your pattern-matching cases can be refactored into a concise

getNthFromEnd n =  (!!n) . reverse

respectively flipping the n argument after the list it is indexing into

(!?) = (!!) . reverse
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This answer has come up in the low-quality posts review queue. The options there are to vote to delete the answer, to edit the answer, or to skip it. Your answer is clearly not a bad suggestion, but this site is Code Review - and to be a review, if you post alternate code, it has to also have a description of why the alternate is better, and what issues in the original code are improved by the alternate code. Right now, your answer is not a review, and should be deleted. \$\endgroup\$ – rolfl Jun 11 '16 at 3:29
  • \$\begingroup\$ This answer is fine, I think. It is obviously simpler than the original code, should be equally performant, and is, in my opinion, easy enough to understand without further explanation. \$\endgroup\$ – 200_success Jun 11 '16 at 4:49

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.