DEV Community

No duplicates challenge in Elm

Anton on May 08, 2019

There is a 99 Elm problems book (originally was for Prolog). Write a function to remove consecutive duplicates of list elements. noDupes [1, 1, ...

Read full post

Avalander • May 9 '19 • Edited

You're forgetting to handle the case of a list with a single element.

Also, in the case x :: y :: xs, when x is not equal to y you should return x :: (noDupes y :: xs) to make sure the rest of the list gets deduplicated.

I don't think you need to handle the case x :: xs at all, but you might need to handle the case of a list with two elements.

Anton • May 11 '19

How do I pattern match on the list with two elements?

noDupes : List a -> List a
noDupes list =
    case list of
        [] -> []
        x::y ->
            if x == y then
                x :: list
            else
                x :: y :: list
        x::y::xs ->
            if x == y then
                x :: noDupes xs
            else
                x :: (noDupes y::xs)

And in the case of two element how do you add that to the rest of the list? As you can see I use "list" in the second case. I don't think it's correct.

Anton • May 11 '19

Now I have some missing possibilities:

This `case` does not have branches for all possibilities:

 9|>    case list of
10|>        [] -> []
11|>        x::y::[]->
12|>            if x == y then
13|>                x :: list
14|>            else
15|>                x :: y :: list
16|>        x::y::xs ->
17|>            if x == y then
18|>                x :: noDupes xs
19|>            else
20|>                x :: (noDupes (y::xs))

Missing possibilities include:

    [_]

I would have to crash if I saw one of those. Add branches for them!

Hint: If you want to write the code for each branch later, use `Debug.todo` as a
placeholder. Read <https://elm-lang.org/0.19.0/missing-patterns> for more
guidance on this workflow.

1hko • May 11 '19 • Edited

You cases check for 1) an empty list, 2) a list with exactly two elements, and 3) a list with 2 elements and a tail. You forgot to check for the singleton list (a list with exactly one element) which is what the compiler is warning you about. Note, checking for a list with exactly two elements is not effective for this particular program.

Anton • May 11 '19

I'm taking a note of "checking for a list with exactly two elements is not effective for this particular program."

Anton • May 11 '19

Interesting this code

noDupes : List a -> List a
noDupes list =
    case list of
        [] -> []

        [x] -> [x]

        x::y::xs ->
            if x == y then
                x :: noDupes xs
            else
                [x]

when applied to

noDupes [ 2, 2, 2, 1, 1, 1 ]

returns

[2, 2]

1hko • May 11 '19 • Edited

the x::y::xs -> case does not recur in the else branch, so an input of [1,2,2,2,3,3,3] will simply return [1] when the first two elements of the input do not match - leaving the [2,2,2,3,3,3] portion completely unprocessed.

1hko • May 11 '19 • Edited

Consider this implementation

noDupes : List a -> List a
noDupes list = 
    case list of
        [] ->
            []

        [ a ] ->
            [ a ]

        a :: b :: more ->
            if a == b then
                noDupes (a :: more)
            else
                a :: noDupes (b :: more)

When we test it

noDupes [1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 4, 4, 4]
-- [ 1, 2, 3, 4, 5, 4 ] : List number

noDupes ["a", "b", "b", "c", "c", "c", "d", "d", "c" ]
-- [ "a", "b", "c", "d", "c" ] : List String

Anton • May 11 '19

I had this noDupes (a :: more) in the else branch when experimented with the code but didn't consider putting that in the first branch.

Thank you. I appreciate your help.

Joseph Stevens • May 11 '19

Haha,I like to think I know FP well, but, when I try to do recursive functions like this, my whole brain freezes up 😅

1hko • May 11 '19 • Edited

It's all about mastering inductive reasoning.

someFunc n = 
    if n == 0 then
        -- do something when n IS zero (base case)
    else
        -- do something where n is (by inductive reasoning) NOT zero

someFunc list =
    if List.isEmpty list then
        -- handle the empty list (base case)
    else
        -- the list (by inductive reasoning) has at least one element

Pattern matching streamlines this for us by allowing us to express the base case and any induction steps using a nice syntax

someFunc n =
    case n of
        0 ->  -- base case
        _ -> -- induction step

someFunc list =
    case list of
        [] -> -- base case
        first :: more -> -- induction step