Elm basics? Applying functions on tuples

[Stefan Schmidt]

Hi all,

motivated by the great responses to my last question and

after reading and experimenting for a while with tuples and destructuring with no avail, 

I hope someone with more experience will be able to easily point me once more in the right directions.

The actual task I want to accomplish implementing following function:

maxNum : List (comparable, number) -> (comparable, number)

The best version I could come up with, which is not working, elm's make never finishes and consumes all memory.

maxNum tuples =

    case tuples of

        x :: xs ->

            Just (List.foldl max (\(_, count) -> count) xs)

        _ ->

            Nothing

2 Problems here:

    1. how do I apply a function over a List of tuples, here for the purpose of finding the maxium count

    2. given the generics comparable and number and that a List may be empty, hence dealing with Maybe (comparable, number)

    How can we achieve: Maybe (comparable, number) -> (comparable, number)

The above then led me to more questions, such as

how to apply functions on parts of tuples

-- sorting List of tuples by the n-th entry within the tuple

given: 

   [(10, "Ralf"), (12, "Peter"), (10, "Peter")]

wanted sort by 1st entry natural order: 

result: 

    [(10, "Ralf"), (10, "Peter"), (12, "Peter")]

wanted sort by 2nd entry natural order: 

result:

    [(10, "Peter"), (12, "Peter"), (10, "Ralf")]

bonus: sort by 1st entry then 2nd entry by a provided custom comparator function: 

result:

    [(10, "Peter"), (10, "Ralf"), (12, "Peter")]

bonus: sorting for any size of tuple, e.g. (10, "Ralf", 19000, 1.80)

given: [(10, "Ralf"), (12, "Peter"), (10, "Peter")]

wanted maximum by 1st entry natural order: 

result: 

    (12, "Peter")

wanted maximum by 2nd entry natural order: 

result:

    (10, "Ralf")

bonus: maximum by 2nd entry then 1st entry by a provided custom function: 

result:

    (12, "Peter")

bonus: maximum/custom function for any size of tuple, e.g. (10, "Ralf", 19000, 1.80)

For completeness these questions are follow ups on the functions derived based on earlier questions

{-| counts the elements of a list by their value using the given function to access the value to count within that list

-}

countsBy : (a -> comparable) -> List a -> List (comparable, Int)

countsBy valueExtractor values =

  values

    |> groupBy valueExtractor

    |> Dict.map (\_ valueGroup -> List.length valueGroup)

    |> Dict.toList

{-| groups the elements of list by their value under a given function

-}

groupBy : (a -> comparable) -> List a -> Dict comparable (List a)

groupBy valueExtractor values =

  let

    update listElem acc =

      let

        listValue =

          valueExtractor listElem

      in

        case Dict.get listValue acc of

          Just values ->

            acc |> Dict.insert listValue (listElem :: values)

          Nothing ->

            acc |> Dict.insert listValue [ listElem ]

  in

    values |> List.foldr update Dict.empty

[Joey Eremondi]

Here's a working version of maxNum. A few things to note:

• I need to use +0 to convince the compiler that you're using numbers, not comparables, for your second tuple elements. I'm pretty sure this is a compiler bug.
• You weren't really using foldl in the way it's intended, which was causing type errors. Foldl takes:
•  a function which takes a new value and the result so far, and generates a new result-so-far
• An initial "result-so-far" value
• The list of values to fold over
  
• In your signature, your return type needs to be a maybe. What is the maxNum of the empty list? In this case, we need Nothing.

To answer your question about going from (Maybe a) to a, you need a default value for a, and then you can use Maybe.withDefault. If there is no default value, then there is no type-safe way to go from Maybe a to a.

Here's the code:

maxNum : List ( comparable, number ) -> Maybe ( comparable, number )

maxNum tuples =
  case tuples of
    x :: xs ->
      Just
        (List.foldl

          (\(( _, count ) as tup) maxSoFar ->
            if count + 0 > (snd maxSoFar) then
              tup
            else
              maxSoFar
          )
          x
          xs
        )

    _ ->
      Nothing

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Max Goldstein]

Thanks Joey. This compiles on elm-lang/try even with the + 0 removed, so is there a smaller, reproducible version of this possible bug?

Also, you can replace _ with an explicit [] match. And for those watching the thread on <|, this is the perfect place to stick it after Just and removed the parens around foldl.

[Joey Eremondi]

@Max: what code exactly are you running? I get an error on /try with the following code:
https://gist.github.com/JoeyEremondi/75f5bf25ca71c77b03fd

It works if you remove the type signature.

On Tue, Mar 1, 2016 at 3:07 PM, Max Goldstein <maxgol...@gmail.com> wrote:

Thanks Joey. This compiles on elm-lang/try even with the + 0 removed, so is there a smaller, reproducible version of this possible bug?

Also, you can replace _ with an explicit [] match. And for those watching the thread on <|, this is the perfect place to stick it after Just and removed the parens around foldl.

--

[Max Goldstein]

Sorry, I didn't have the type signature when I ran it.

Yes, that's a bug: https://github.com/elm-lang/elm-compiler/issues/1281

[Stefan Schmidt]

That helped a lot, thank you!

I ended up rewriting it for myself for clarity, it takes time for me to get used to the functional code style.

For some reason the compiler complains about "Maybe":

But for good reason I don't want to return a Maybe, I want to return a default tuple provided on function call.

maxNum : List (comparable, number) -> (comparable, number) -> (comparable, number)

maxNum tuples default =

  let

    max tuple1 tuple2 =

        let

            (_, count1) = tuple1

            (_, count2) = tuple2

        in

            if count1+0 > count2+0 then

                tuple1

            else

                tuple2    

  in

  case tuples of

    x :: xs ->

        Just <| List.foldl max x xs

    [] ->

        Just default

main = Graphics.Element.show <|

    maxNum [("x",2),("y",1),("z",3)] ("n/a",0)

Compiler complains:

The type annotation is saying: List ( comparable, number ) -> ( comparable, number ) -> ( comparable, number ) But I am inferring that the definition has this type: List ( comparable, number ) -> ( comparable, number ) -> Maybe ( comparable, number )

Why is that?

I'm always returning a tuple, or am I mistaken?

Thanks for reading!

[Joey Eremondi]

Just is a Constructor for Maybe. Get rid of it and I think you'll be OK.

--

[Erkal Selman]

Use the handy functions from the core library.

For example List.sortBy fst sorts a List of tuples according to the values of the first entries of its elements. 

In order to sort by the second entries, use List.sortBy snd.

(See the code below.)

Use the Order type from the core library to define your own comparator function.

About your "take-the-maximum" function: 

You can first sort the list and take the head with the List.head.

This returns a Maybe type, which is a very good thing!

The language forces us to handle the case in which the list is empty. 

By returning a Maybe type, it permits you to define functions which could cause run-time errors. 

At start, this feature of the language will bother you, but later on, you will be thankful to it.

One handles the Maybe types with pattern matching. 

In some cases you really want your program to crash, if for example you get Nothing as output. 

For this, you can use Debug.crash.

You can copy-paste the following code into elm-try:

import Html exposing (Html, div, p, text)

main : Html

main =

  div

    []

    [ p [] [ text (toString (data |> sortByFirst)) ]

    , p [] [ text (toString (data |> sortBySecond)) ]

    , p [] [ text (toString (data |> sortByFstThenBySecond compare compare)) ]

    ]

data : List ( number, String )

data =

  [ ( 10, "Ralf" ), ( 12, "Peter" ), ( 10, "Peter" ) ]

{-| sort by 1st entry natural order:

result:

    [(10, "Ralf"), (10, "Peter"), (12, "Peter")]

-}

sortByFirst : List ( comparable, a ) -> List ( comparable, a )

sortByFirst =

  List.sortBy fst

{-| sort by 2nd entry natural order:

result:

    [(10, "Peter"), (12, "Peter"), (10, "Ralf")]

-}

sortBySecond : List ( a, comparable ) -> List ( a, comparable )

sortBySecond =

  List.sortBy snd

{-| sort by 1st entry then 2nd entry by a provided custom comparator functions:

result:

    [(10, "Peter"), (10, "Ralf"), (12, "Peter")]

-}

type alias Comparator a =

  a -> a -> Order

sortByFstThenBySecond : Comparator a -> Comparator b -> List ( a, b ) -> List ( a, b )

sortByFstThenBySecond firstComparator secondComparator =

  let

    ordering ( u1, u2 ) ( v1, v2 ) =

      case ( firstComparator u1 v1, secondComparator u2 v2 ) of

        ( LT, _ ) ->

          LT

        ( EQ, LT ) ->

          LT

        ( EQ, EQ ) ->

          EQ

        otherwise ->

          GT

  in

    List.sortWith ordering

[Joey Eremondi]

You're probably better using maximumBy from list-extra, instead of sortBy, since it will only be O(n), whereas sorting the list then taking the head will be O(n log n), especially since Elm isn't lazy like Haskell.

You'll have to deal with the Maybe in either case, since taking the head of a list will return Maybe.

--

[Max Goldstein]

+1 for maximumBy, but I think even in a lazy language you'd have to run the entire sort before taking the head.

[Janis Voigtländer]

Depends on the sort. For a typical implementation of insertion sort in Haskell, the function min list = head (sort list) finds the minimum in O(length of the list).

​

2016-03-03 20:20 GMT+01:00 Max Goldstein <maxgol...@gmail.com>:

+1 for maximumBy, but I think even in a lazy language you'd have to run the entire sort before taking the head.

--