No duplicates challenge in Elm

Publish Date: May 8 '19

14 11

There is a 99 Elm problems book (originally was for Prolog).

Write a function to remove consecutive duplicates of list elements.

noDupes [1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 4, 4, 4]
    == [1, 2, 3, 4, 5, 4]

I'm doing something wrong here. Am I on the track or completely off track?

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

The compiler already gave me a heads up that I'm comparing an element to a list:

17|             if x == xs then
                   ^^^^^^^
The left side of (==) is:

    a

But the right side is:

    List a

Different types can never be equal though! Which side is messed up?

Hint: Did you forget to add [] around it?

Interesting I just wrapped the x in [x]. But I now have the second the last case to deal with.

Comments 11 total

AvalanderMay 9, 2019

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.
- AntonMay 11, 2019
  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.
- AntonMay 11, 2019
  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.
  - 1hkoMay 11, 2019
    
    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.
    - AntonMay 11, 2019
      
      I'm taking a note of "checking for a list with exactly two elements is not effective for this particular program."
AntonMay 11, 2019
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]
- 1hkoMay 11, 2019
  
  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.

Joseph StevensMay 11, 2019

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

1hkoMay 11, 2019

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

1hkoMay 11, 2019

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

AntonMay 11, 2019

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.

Add comment

Anton @antonrich

No duplicates challenge in Elm

Comments 11 total