Functional programming 1:1 - How to count unique elements in a list?

[Stefan Schmidt]

I've recently discovered Elm and I enjoy it quite a bit.

However I struggle with a few concepts and my limited ability to think in "functional programming".

For instance I would like to know and understand how to combine functions to count unique elements in a list.

Given this list:

data =

    ["a", "b", "a", "d", "d", "c"]

I would like to apply a function which results in another list grouping the occurrences with the count, e.g. 

    [("a",2), ("b", 1), ("d",2),("c",1)]

Assume we have now a list of records, e.g. person information:

complexData =

    [ { age = 10, name = "Ralf" }, { age = 10, name = "Peter" }, { age = 12, name = "Peter" } ]

I would like to apply a function to retrieve:

    [ ({age = 10}, 2), ({age = 12}, 1) ]

and another function to retrieve:

     [ ({ name = "Ralf" }, 1),  ({ name = "Peter" }, 2) ]

Besides solutions, I'm also very much interested in understanding the approach and logic. I'm sure there are some good readings and videos out there, but it's difficult to filter through so much noise.

[Daniel Bachler]

Hi Stefan,

maybe someone else can give you more pointers as I don't have the time right now to write down the solution to your problem - but in the mean time I think it might help you to know that in a purely functional language, what you are looking for is to "fold" your list into a Dict. Folds are aka as "reduce", so what you do is use the fold to traverse the list and build up a new dictionary that contains the information in the format you are after.

If you are still struggling tomorrow and no one else answers I'll write down a possible solution.

[Peter Damoc]

The first FP tool that popped into my mind looking at what you want to achieve is a `fold`

a `fold` or `reduce` is a way to convert a list of things into a single value. 

foldl (+) 0 [1,2,3,4,5]  -- this folds the list into the sum of elements. 

However, you can fold a list and produce another list. 

foldl (::) [] [1,2,3] == [3,2,1] 

in your case I would use a dictionary where I would get the current element with a default of 1 and just accumulate on each incidence. 

here is some code to show a primitive implementation:

import Html exposing (..) 

import Dict 

sample = ["a", "b", "a", "d", "d", "c"]

complexData =

    [ { age = 10, name = "Ralf" }, { age = 10, name = "Peter" }, { age = 12, name = "Peter" } ]

foldF x dict =

  let 

    updateF mv =

      case mv of 

        Nothing -> Just 1

        Just v -> Just (v+1)

  in        

   Dict.update x updateF dict

simpleFold = List.foldl foldF Dict.empty sample

complexFold toS x dict =

  let 

    updateF mv =

      case mv of 

        Nothing -> Just 1

        Just v -> Just (v+1)

  in        

   Dict.update (toS x) updateF dict

  

ageToS x = "{age = " ++ (toString (.age x)) ++ "}" 

nameToS x = "{name = \"" ++ (.name x) ++ "\"}" 

complexFoldedAge = List.foldl (complexFold ageToS)  Dict.empty complexData

complexFoldedName = List.foldl (complexFold nameToS)  Dict.empty complexData

main = 

  div []

  [ text <| toString simpleFold

  , br [] []

  , text <| toString complexFoldedAge

  , br [] []

  , text <| toString complexFoldedName

  ]

--
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.

--

There is NO FATE, we are the creators.
blog: http://damoc.ro/

[Alexey Shamrin]

Using List.Extra.span (and inspired by List.Extra.groupBy):

module Group where

import List.Extra exposing (span)

countingGroupBy : (a -> b) -> List a -> List (b, Int)
countingGroupBy key xs' =
  let
    eq a b = key a == key b

  in
    case xs' of
      [] ->
        []

      (x::xs) ->
        let
          (ys, zs) = span (eq x) xs
        in
          (key x, (List.length ys) + 1) :: countingGroupBy key zs


countingGroup = countingGroupBy identity

$ eql-repl
> import Group
> Group.countingGroupBy .age [ { age = 10, name = "Ralf" }, { age = 10, name = "Peter" }, { age = 12, name = "Peter" } ]

[(10,2),(12,1)] : List ( number, Int )
> Group.countingGroup ["a", "b", "a", "d", "d", "c"]
[("a",1),("b",1),("a",1),("d",2),("c",1)] : List ( String, Int )

[Max Goldstein]

You can also look at the multiset library:

http://package.elm-lang.org/packages/mgold/Elm-Multiset/1.0.5/Multiset

In particular fromList. It uses the Dict based approach described above.

[Alexey Shamrin]

$ eql-repl

Correction:

$ elm-package install --yes circuithub/elm-list-extra
$ elm-repl

[Alexey Shamrin]

I've just realised you also want to group non-consequent sets of values. Sorting will help in this case:

> [ { age = 10, name = "Ralf" }, { age = 10, name = "Peter" }, { age = 12, name = "Peter" } ] |> List.sortBy .age |> Group.countingGroupBy .age

[(10,2),(12,1)] : List ( number, Int )

> ["a", "b", "a", "d", "d", "c"] |> List.sort |> Group.countingGroup
[("a",2),("b",1),("c",1),("d",2)] : List ( String, Int )

Updated code (with examples) lives at gist now.

[Stefan Schmidt]

Huge thanks to everyone who replied.

Very insightful and useful.

Attacking the problem from different angles, i.e. implement using existing core features or using additional libraries.

I came across the sort/group solution when I googled for an implementation in Haskell, but didn't know where to find a library for that.

I'll take some more time to fully digest it, but already got a much clearer picture.

Great community!

[Erkal Selman]

For this kind of simple task, one should avoid using libraries.

Here is another solution. It works, if you copy-paste it into elm-try.

It hink that the `groupBy` function is so useful on its own,

  that it should be even included in the standard List library.

import Dict exposing (Dict)

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

main : Html

main =

  div

    []

    [ p [] [ text (toString (data |> countsBy identity)) ]

    , p [] [ text (toString (complexData |> countsBy .age)) ]

    , p [] [ text (toString (complexData |> countsBy .name)) ]

    ]

data : List String

data =

  [ "a", "b", "a", "d", "d", "c" ]

complexData : List { age : number, name : String }

complexData =

  [ { age = 10, name = "Ralf" }, { age = 10, name = "Peter" }, { age = 12, name = "Peter" } ]

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

countsBy f l =

  l

    |> groupBy f

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

    |> Dict.toList

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

-}

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

groupBy f l =

  let

    upd e acc =

      let

        fe =

          f e

      in

        case Dict.get fe acc of

          Just l' ->

            acc |> Dict.insert fe (e :: l')

          Nothing ->

            acc |> Dict.insert fe [ e ]

  in

    l |> List.foldr upd Dict.empty

On Friday, February 26, 2016 at 12:29:21 PM UTC+1, Stefan Schmidt wrote: