A simple list recursion problem: how do I do this?

[polarit]

@lydell

Turns out it’s literally the definition of List.map2

Well, this out-of topic is too interesting to be closed.
I just wanted to tell about the “exercise”, I made for my self. I wanted to see, how easy or difficult it is to pick up an indexed tuple from the list. Result: extremely easy.

> f1
["I","meant","that","any","time","you","do","you","could","just","as","well","do"]
> f2
[(0,"I"),(1,"meant"),(2,"that"),(3,"any"),(4,"time"),(5,"you"),(6,"do"),(7,"you"),(8,"could"),(9,"just"),(10,"as"),(11,"well"),(12,"do")]
    : List ( Int, String )
>checkIndex : (Int, a) -> Int
| checkIndex tup =
|   Tuple.first tup
|   
<function> : ( Int, a ) -> Int
> checkIndex (10,"Just")
10 : Int
>  List.filter (\n -> checkIndex n == 9) f2
[(9,"just")] : List ( Int, String )

So I see now, it makes sense to create an indexed list just with tuples.
I watched too elm core source at your link to GH - pretty large, contains almost everything in compact form.
I hope, this discussion was not too boring for you. For me it was usefull and I enjoyed a lot.

[badlydrawnrob]

I can’t seem to alter the posts after a couple of days. Shame, else I would’ve added those new suggestions to the “solution”.

Do you know Julian date number? You can easily calculate the weekdays for the given Julian date

@polarit I’m not a maths person, explain how modBy manages to do that? This seems theoretically cool, but relies on building out a library for that functionality. I’m not sure how practical that would be as appose to using Elm’s time package

> import List.Extra exposing (zip)
> zip wdNrs wdNames
[(1,"Mon"),(2,"Tue"),(3,"Wed"),(4,"Thu"),(5,"Fri"),(6,"Sat"),(7,"Sun")]
    : List ( Int, String )

The zip function is also cool, though might be better calling getIndex function on wdNames (at least if there’s an unknown length to the list).

getIndex list =
    (range 0 ((List.length list - 1)))

Again like you’ve both noted, I’m not sure how much we’d need to worry about speed — “Shape of a function” is quite a good bit of SICP and brings up these questions:

• Is a flat shape considered faster and more performant?
• Is there an Elm stepper repl somewhere, like Dr. Racket?
• Or any good guides you could pass on for performance?

@lydell

Turns out it’s literally the definition of List.map2 (except my off-by-1-error-that-really-doesn’t-matter): core/src/List.elm at 65cea00afa0de03d7dda0487d964a305fc3d58e3 · elm/core · GitHub

@lydell So both List.map2 and List.indexedMap are the same speed?

Summing up

I’ve created a final little program mushing together what’s been talked about. Judging by what we’ve covered in this thread, keeping things concise and making use of built-in List functions makes things a whole lot easier to reason about. My first attempt is a lot harder to follow.

I wish there was a function that did everything from line 33 onwards though. You’ve still got to do something like this to make use of all our hard work:

pluckDay : Index -> Day
pluckDay i =
    case (List.head (filterDay i)) of
        Just day ->
            (Tuple.second day)
        Nothing ->
            "It's always a Monday!"

Going forward

So there’s a few questions we’ve covered, or that I need to consider further (don’t worry I’m not looking for answers!):

1. When should I use a recursive function? (when it’s simple, I would say)
2. When is it wiser to use a built in List function? (most of the time it seems)
3. What to do about finite lists? (use a Set DayTuple?)
4. Using a simple case -vs- creating a Tuple.pair (the simple case might actually be preferable)
5. “Plucking” the DayTuple we want to use (remove as many steps as you can to get to this point)
6. If we were building a simple calendar, say, what’s the sane way to do this with existing libraries? (using Time etc)

I guess this is all good practice and, although I think the solution I’ve linked to might be overkill for a simple day-finder, it’s been a good exercise seeing what’s possible with Elm.

It seems a good many things are already “solved problems” in the core libraries!

Thanks guys

---

Useful functions for recursion:

map, map2, indexedMap (the example there does everything I wanted), zip as an alternative to indexedMap, and filter. The rest you can see in the examples above.

[polarit]

@badlydrawnrob

I’ve created a final little program mushing together what’s been talked about.

So, it works!
Just a little remark assuming that you are doing something to production needing optimizing.
Then you compile the source with option --optimize but optimizer wiil warn about any use of Debug.toString.
That means, all debugs must be removed or replaced with alternative code.
Example
Complled without optimization

 elm make Badly.elm --output=elm.js
Success! Compiled 1 module.

Main ───> elm.js

92723 6 Feb 20:07 elm.js
Next, trying to optimize:

% elm make Badly.elm --optimize --output=elm.min.js

Success! Compiled 1 module.
-- DEBUG REMNANTS ------------------------------------------

There are uses of the `Debug` module in the following modules:

    Main

But the --optimize flag only works if all `Debug` functions are removed!

This may be improved so that debug is removed:

main =
    Html.text (Debug.toString (pluckDay 2))

main =
    Html.text (pluckDay 2)

Note, the result of pluckday 2 is a String, so it does not need any conversion

toString

.
We try recompile after correction:

% elm make Badly.elm --optimize --output=elm.min.js
Success! Compiled 1 module.

    Main ───> elm.min.js

That is reduced by 700 bytes only but after running with minify.sh it’s only this size:

7834  6 Feb 21:11 elm.min.js

I’ll return to other points later, if I find something more.

=========================================
Later today…
I made some little changes to your code allthough it seems to be all Ok.
It can be seen on this new version.

I replaced your function pluckDay using the cases with the function pickDay using Maybe.withDefault.
I prefer it always to cases if possible.
It could be modified further to give Default text different from “Monday” for incorrect indexes (so as you already made):

pickDay i =
    Maybe.withDefault  (0, "Monday else") (List.head (filterDay i))
    |> Tuple.second

[badlydrawnrob]

Do you mean you used this package to minify? Or does --optimize do the job?

ah so if it’s a string, no need to convert. Still getting used to implementing main. It’s certainly looking way better than my original attempts. Maybe.withDefault looks very handy (constantly having to case on Maybe is a bit of a drag).

I’ve actually been experimenting with No Code solutions like this one so until my Elm skills improve it’s likely going to be a hybrid. The HTML that WeWeb converts to is sometimes awful, though!

Nice work!

[lydell]

@badlydrawnrob

@lydell So both List.map2 and List.indexedMap are the same speed?

First I thought List.indexedMap was implemented with JavaScript, more lower level than is possible in pure Elm code and therefore had “unfair” better performance than zipping with a list of indexes. Then I learned that it’s actually implemented using List.map2 and List.range behind the scenes, so my claim about performance was clearly wrong.

@badlydrawnrob

I wish there was a function that did everything from line 33 onwards though.

What you’re really doing, is taking an item at a certain index out of that daysOfWeek list. You can use List.Extra.getAt for that, which makes the code very concise: https://ellie-app.com/qffcNJ4VRS6a1 (But not as performant as the simple case-of on the indexes.)

---

Regarding your question about when to use recursion and when to use helper functions.

A recursive function can do anything. A type annotation on it gives clues, but I kind of have to read the whole thing and think about it to see exactly what it does. But when I come across code that uses List.map I instantly know a couple of things:

1. The output is going to be a list.
2. The output list is going to have the same length (we are not discarding any elements).
3. Each item is going to be transformed in isolation – they don’t depend on each other.

And when I see List.filter I instantly know that I will get the same type of list back, just with potentially fewer items in it. And so on with other helper functions.

So if I have a bug where one row in a shopping cart (of an imaginary e-commerce website) somehow disappears, I know that a List.map call won’t be the culprit, but a List.filter call could be. Likewise, if a product price in the shopping cart is displayed wrong, it’s the other way around – List.filter can’t change it, but a List.map can. But if you chose to use a recursive function where you could have used List.map or List.filter I can’t rule it out when hunting for my bug, since it could do anything.

I use a recursive function only when:

1. What I’m trying to do is not possible with any available helper functions.
2. A recursive functions performs better, and it matters. For example, with a recursive function you can go through a couple of items in a list, and then stop early once you’ve reached some condition, while most list helper functions always go through the entire list.
3. When a recursive function ends up easier to read than say a complicated List.foldl.
4. I’m writing something for fun. I like recursion

[polarit]

@badlydrawnrob

Do you mean you used this package to minify? Or does --optimize do the job?

I could not find the original minify.sh which I have slightly modified to my use.
That is especially for Elm-files and it does all; make → optimize → uglify → compact ,…
from source.elm to elm.min.js
running in Mac OS bash shell very quickly
You can download it from GitHub.
I hope it works also for you. Pls, open it first in editor, so you see what changes shall be done if used in your system - probably only few if any.

[benjamin-thomas]

I would also add that if you compare the reverse function I mentioned earlier with List.foldl, you will see that they are very similar.

Meaning you can implement reverse with List.foldl.

So you use recursion any time you need to loop, whether you do it explicitly or via a” higher order function"

[polarit]

I have sent earlier today a PM to you about minifier to elm but don’t know, whether you received it.

Another way to search daynames from a list is using function getAt , library List.Extra.
See this!
Only negative thing, getAt does give damn Maybe again which I solved with Maybe.withDefault.

[polarit]

@benjamin-thomas

Meaning you can implement reverse with List.foldl.

Yes!

> List.foldl (::) [] [1,2,3] == [3,2,1]
True : Bool
> (String.fromList <| List.foldl (::) [] <| String.toList "abcdefg") == "gfedcba"
True : Bool 

trying to use cons with foldl…

demo = Debug.toString (List.foldl cons [] [1,2,3,4])
NAMING ERROR
Jump to problem
I cannot find a `cons` variable:

54| demo = Debug.toString (List.foldl cons [] [1,2,3,4])

                                      ^^^^
These names seem close though:

cons is not exposed in List although used there internally, thus it must be defined explicitly if needed:

cons :  a -> List a -> List a
cons =
   (::)

As soon as cons is defined, it works:

> demo = Debug.toString (List.foldl cons [] [1,2,3,4])
"[4,3,2,1]" : String
> 

[Bram]

Just as a sidenote for those who are curious, this is actually how List.reverse is implemented in the elm/core library.

{-| Reverse a list.


    reverse [1,2,3,4] == [4,3,2,1]
-}
reverse : List a -> List a
reverse list =
  foldl cons [] list

[badlydrawnrob]

@lydell

What you’re really doing, is taking an item at a certain index out of that daysOfWeek list. You can use List.Extra.getAt for that, which makes the code very concise: https://ellie-app.com/qffcNJ4VRS6a1 (But not as performant as the simple case-of on the indexes.)

@lydell So in general would you suggest using case with indexes before using List.Extra.getAt or Array.get; and those before a more convoluted example like building a List Tuple, if performance is a concern? Or is it a case of “it depends” (on how they’re used in a program)?

• Where can I go to find out more about performance with Elm for these kind of decisions?

@lydell

But when I come across code that uses List.map I instantly know a couple of things: … And when I see List.filter I instantly know that I will get the same type of list back …

That’s an interesting way to look at things. It does sound to be easier to reason about with built-in functions.

---

@polarit I responded with a PM. I think I’ll worry about optimisation later. As I mentioned above, I think I need to learn a bit more about performance and speed in general — I think a flatter procedure shape runs faster, but in that link it says:

A word of advice: Get your software working first , then worry about profiling and optimizations. Many programmers get stuck in hyper-optimizing their code without first finishing to see where the true bottlenecks lie. You can spend weeks gaining a 1% performance boost utilizing arcane algorithms when it turns out that a 5-minute tweak could net you a 50% boost.

• Any suggestions of a general package for testing bottlenecks would be very helpful for later on.

---

@polarit @benjamin-thomas @Bram Very cool, thank you!

I’m not 100% sure how this works however. Firstly, cons seems to be only available internally (not exposed with List), and secondly “stepping through” this function — is this correct?

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

    x :: xs ->
      foldl func (func x acc) xs


foldl (::) [] [1,2,3]
--         ^^                  -- The original accumulator
foldl (::) ((::) 1 []) [2,3]). -- Does ((::) 1 []) return [1] straight away?
--         ^^^^^^^^^^^         -- This value is now the accumulator
foldl (::) ((::) 2 [1]) [3])

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

-- `[] -> acc`  base case returns the accumulator

[3,2,1]

At first I thought [] -> accum was somehow setting the accumulator variable; now (I think) I see the original accumulator argument is passing through to (func x acc) and the base case [] -> acc is returning that accumulator on the final loop?

• I find this bit of the type annotation hard to follow:
  • foldl : (a -> b -> b) -> b ->.

---

The structure of a list in Haskell written in this form is more like Lisp to me. So you could write it like:

cons = (::)

(cons 3 (cons 2 (cons 1 [])))

[benjamin-thomas]

@badlydrawnrob

I’m not 100% sure how this works however

Here’s what’s going on. You can type this in the REPL.

-- That's the long version
> List.foldl (\x acc -> x :: acc) [] [1,2,3]
[3,2,1] : List number

You can give a name to the anonymous function:

> accum = \x acc -> x :: acc
-- Now call it
> List.foldl accum [] [1,2,3]
[3,2,1] : List number

The function accum can be represented in other ways:

accum = \x acc -> x :: acc
-- same as
accum x acc = x :: acc
-- same as
accum x acc = (::) x acc
-- same as
accum x = (::) x
-- same as
accum = (::)

Personally I prefer not to condense code too much, unless its particularly appropriate.

Now lists in Elm are linked lists, like in Lisp.

And this:

(1 :: (2 :: (3 :: [])))

Is equivalent to this:

1 :: 2 :: 3 :: []

(I think due to operator precedence)

The connection to Lisp you are looking for is probably this:

cons = (::)
> (cons 1 (cons 2 (cons 3 [])))
[1,2,3] : List number

In Lisp:

> (cons 1 (cons 2 (cons 3 '())))
'(1 2 3)

[badlydrawnrob]

@benjamin-thomas

List.foldl (\x acc -> x :: acc) [] [1,2,3]

@benjamin-thomas Thanks for breaking that down for me. It helps thinking about it in various ways. In case anyone’s interested I coded it up in Lisp too:

;; `cons` is equivalent to (::)
;; f = function
;; a = accumulator

(define (fold-left f a list)
  (cond
    [(empty? list) a]
    [else (fold-left f (f (first list) a)
                   (rest list))]))

(fold-left cons '() '(1 2 3))

And using Dr.Racket’s stepper, reverse using foldl does seem to function as I imagined:

@badlydrawnrob

cons = (::)

foldl cons [] [1,2,3]
--         ^^                  -- The original accumulator
foldl cons (cons 1 []) [2,3]). -- (cons 1 []) returns [1]
--         ^^^^^^^^^^^         -- This value is now the accumulator
foldl cons (cons 2 [1]) [3])
foldl cons (cons 3 [2,1]) [])

-- `[] -> acc`  base case returns the accumulator
[3,2,1]

I think we can start closing out this thread now, as it’s become a little more involved than I originally intended! I’ll split out individual questions to another thread if I have them.

Thanks all!