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

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.

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

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

=========================================
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
``````

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!

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.

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
2 Likes

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

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"

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.

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

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
``````
2 Likes

@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?

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 `acc`umulator variable; now (I think) I see the original `acc`umulator 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 [])))
``````

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)
``````
1 Like

@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:

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!

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.