Avatar of paulfioravanti

paulfioravanti's solution

to List Ops in the Elm Track

Published at Jul 30 2019 · 0 comments
Instructions
Test suite
Solution

Implement basic list operations.

In functional languages list operations like length, map, and reduce are very common. Implement a series of basic list operations, without using existing functions.

The precise number and names of the operations to be implemented will be track dependent to avoid conflicts with existing names, but the general operations you will implement include:

  • append (given two lists, add all items in the second list to the end of the first list);
  • concatenate (given a series of lists, combine all items in all lists into one flattened list);
  • filter (given a predicate and a list, return the list of all items for which predicate(item) is True);
  • length (given a list, return the total number of items within it);
  • map (given a function and a list, return the list of the results of applying function(item) on all items);
  • foldl (given a function, a list, and initial accumulator, fold (reduce) each item into the accumulator from the left using function(accumulator, item));
  • foldr (given a function, a list, and an initial accumulator, fold (reduce) each item into the accumulator from the right using function(item, accumulator));
  • reverse (given a list, return a list with all the original items, but in reversed order);

Elm Installation

Refer to the Installing Elm page for information about installing elm.

Writing the Code

The first time you start an exercise, you'll need to ensure you have the appropriate dependencies installed. Thankfully, Elm makes that easy for you and will install dependencies when you try to run tests or build the code.

Execute the tests with:

$ elm-test

Automatically run tests again when you save changes:

$ elm-test --watch

As you work your way through the test suite, be sure to remove the skip <| calls from each test until you get them all passing!

Submitting Incomplete Solutions

It is possible to submit an incomplete solution so you can see how others have completed the exercise.

Tests.elm

module Tests exposing (tests)

import Expect
import ListOps exposing (append, concat, filter, foldl, foldr, length, map, reverse)
import Test exposing (..)


tests : Test
tests =
    describe "List Ops"
        [ describe "length"
            [ test "empty list" <|
                \() -> Expect.equal 0 (ListOps.length [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal 4 (ListOps.length (List.range 1 4))
            ]
        , describe "reverse"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal [] (ListOps.reverse [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal [ 4, 3, 2, 1 ] (ListOps.reverse (List.range 1 4))
            ]
        , describe "map"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal [] (ListOps.map ((+) 1) [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal (List.range 2 5) (ListOps.map ((+) 1) (List.range 1 4))
            ]
        , describe "filter"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal [] (ListOps.filter (\_ -> True) [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal [ 2, 4 ] (ListOps.filter (\x -> modBy 2 x == 0) (List.range 1 4))
            ]
        , describe "foldl"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal 0 (ListOps.foldl (+) 0 [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal 10 (ListOps.foldl (+) 0 (List.range 1 4))
            , skip <|
                test "direction" <|
                    \() -> Expect.equal [ 4, 3, 2, 1 ] (ListOps.foldl (::) [] (List.range 1 4))
            ]
        , describe "foldr"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal 0 (ListOps.foldr (+) 0 [])
            , skip <|
                test "non-empty list" <|
                    \() -> Expect.equal 10 (ListOps.foldr (+) 0 (List.range 1 4))
            , skip <|
                test "direction" <|
                    \() -> Expect.equal (List.range 1 4) (ListOps.foldr (::) [] (List.range 1 4))
            ]
        , describe "append"
            [ skip <|
                test "empty lists" <|
                    \() -> Expect.equal [] (ListOps.append [] [])
            , skip <|
                test "empty and non-empty lists" <|
                    \() -> Expect.equal (List.range 1 4) (ListOps.append [] (List.range 1 4))
            , skip <|
                test "non-empty and empty lists" <|
                    \() -> Expect.equal (List.range 1 4) (ListOps.append (List.range 1 4) [])
            , skip <|
                test "non-empty lists" <|
                    \() -> Expect.equal (List.range 1 8) (ListOps.append (List.range 1 4) (List.range 5 8))
            ]
        , describe "concat"
            [ skip <|
                test "empty list" <|
                    \() -> Expect.equal [] (ListOps.concat [])
            , skip <|
                test "list of lists" <|
                    \() -> Expect.equal (List.range 1 10) (ListOps.concat [ List.range 1 3, [], List.range 4 7, List.range 8 10 ])
            ]
        ]
module ListOps exposing
    ( append
    , concat
    , filter
    , foldl
    , foldr
    , length
    , map
    , reverse
    )


length : List a -> Int
length list =
    case list of
        [] ->
            0

        _ :: tail ->
            1 + length tail


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

        head :: tail ->
            reverse tail ++ [ head ]


foldl : (a -> b -> b) -> b -> List a -> b
foldl f acc list =
    case list of
        [] ->
            acc

        head :: tail ->
            foldl f (f head acc) tail


foldr : (a -> b -> b) -> b -> List a -> b
foldr f acc list =
    case list of
        [] ->
            acc

        head :: tail ->
            f head (foldr f acc tail)


map : (a -> b) -> List a -> List b
map f list =
    case list of
        [] ->
            []

        head :: tail ->
            f head :: map f tail


filter : (a -> Bool) -> List a -> List a
filter f list =
    case list of
        [] ->
            []

        head :: tail ->
            if f head then
                head :: filter f tail

            else
                filter f tail


append : List a -> List a -> List a
append xs ys =
    case ( xs, ys ) of
        ( [], [] ) ->
            []

        ( xs_, [] ) ->
            xs_

        ( [], ys_ ) ->
            ys_

        ( xs_, ys_ ) ->
            foldr (::) ys_ xs_


concat : List (List a) -> List a
concat list =
    case list of
        [] ->
            []

        head :: tail ->
            foldr (::) (concat tail) head

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?