loading...

Can you spot the problem in the implementation of nthElement?

dwayne profile image Dwayne Crooks ・1 min read

There is a problem with this implementation of nthElement:

nthElement : List a -> Int -> Result String a
nthElement list n =
  if n >= 0 then
    nthElementHelper list n
  else
    Err ("The index must be non-negative: " ++ String.fromInt n)

nthElementHelper : List a -> Int -> Result String a
nthElementHelper list n =
  case list of
    [] ->
      Err ("List too short by " ++ String.fromInt (n+1) ++ pluralize n "element" "elements")

    x :: rest ->
      if n == 0 then
        Ok x
      else
        nthElementHelper rest (n-1)

Can you spot the problem and fix it so that it passes all the following tests?

nthElement : Test
nthElement =
  describe "nthElement"
    [ describe "empty list"
        [ fuzz Fuzz.int "can never find the nth element of the empty list" <|
            \n ->
              Ch1.nthElement [] n
                |> Expect.err
        ]
    , describe "non-empty list"
        [ test "it returns the 1st element" <|
            \_ ->
              Ch1.nthElement [1, 2, 3, 4, 5] 0
                |> Expect.equal (Ok 1)
        , test "it returns the 2nd element" <|
            \_ ->
              Ch1.nthElement [1, 2, 3, 4, 5] 1
                |> Expect.equal (Ok 2)
        , test "it returns the 5th element" <|
            \_ ->
              Ch1.nthElement [1, 2, 3, 4, 5] 4
                |> Expect.equal (Ok 5)
        , test "it returns an error given a negative index" <|
            \_ ->
              Ch1.nthElement [1, 2, 3, 4, 5] -1
                |> Expect.equal (Err "The index must be non-negative: -1")
        , test "it returns an error given an out of bounds index" <|
            \_ ->
              Ch1.nthElement [1, 2, 3, 4, 5] 5
                |> Expect.equal (Err "List too short by 1 element")
        ]
    ]

Share your thoughts in the comments below.

P.S. I personally made this error and I found it due to the tests. Tests can still be useful even in a typed functional language.

Posted on Aug 7 '19 by:

dwayne profile

Dwayne Crooks

@dwayne

A full stack web developer who has an interest in programming language theory, interpreters, compilers and type theory. I enjoy programming with Elm and Haskell in my free time.

Discussion

markdown guide
 

Just by a quick glance I'd say that your pluralise method isn't fed the proper number.
It should be (n+1) to get the remaning length I guess.

I'll have another look at it later :)

 

+1

That's partially correct. There's one more thing you missed.

 

it lacks a space here too

... String.fromInt (n+1) ++ pluralize n ...

here you'll get something like 1elements instead of 1 elements

to be honest I'd rather use something like elm-string-interpolate to avoid having to think of these string concatenations :)

it lacks a space here too

precisely

to be honest I'd rather use something like elm-string-interpolate to avoid having to think of these string concatenations

I won't add a dependency just for that. But, the way I wrote it did lead to a subtle bug so maybe doing it in the following way would have been clearer:

String.join " "
  [ "List too short by"
  , String.fromInt (n+1)
  , pluralize (n+1) "element" "elements"
  ]

I would add a deps for this :D it's just in my test-deps, besides it might be useful in the rest of your app. I mean in the front-end we often have to show text with some values that we fetch from different places: using an utility or making your own to get that type of code:

"List too short by {} element{}" |> interpolate [ String.fromInt (n+1), pluralize (n+1) "" "s"]  

furthermore, I'd actually make a interpolate function that takes a list of a custom type:

1st define a type like this:

type InterpolationValue a
    = IntValue Int
    | StringValue String
    | CurrencyValue Float 
    | ... 
    | CustomValue (a -> String) a

this way my interpolate function would look like this:

interpolate: List InterpolationValue -> String -> String

then I think my code would be much easier to read and also potentially much easier to i18nize it later on :)

But that's again just a matter of personal taste!

To be clear, I really meant that in this project that I'm working on I won't add a dependency for it. Since this particular function, nthElement, is quite insignificant.

However, I do agree that if I'm working on a project where I am doing a lot of this sort of stuff then abstracting the task will have its benefits.

This discussion reminds me of Formatting in Haskell. Which I first came across in "Related Work" in url's README.

Sorry I didn't mean to come across aggressive or arogant :)

the formatting article is an interesting read! thanks for the link.

Sorry I didn't mean to come across aggressive or arogant

I didn't think so at all. But, no worries. Thanks for sharing your thoughts. I appreciated it.

Cheers mate.
Keep up writing, your posts are cool!

 

you could perhaps optimize it to leverage the "tail-recurssive" optimization by doing something like this btw:

nthElementHelper : List a -> Int -> Result String a
nthElementHelper list n =
  case (n, list) of
    (_, []) ->
      Err ("List too short by " ++ String.fromInt (n+1) ++ pluralize n "element" "elements")

    (0, x :: _) ->
      Ok x
    (nth, _ :: rest) ->
      nthElementHelper rest (nth-1)
 

although come to think of it you're already doing "tail-recurssion"

 

yeah, I'm already doing that

I still prefer the case of on a tuple than a case of with some if then else branching inside but that's personal taste :)