[elm-discuss] Looping While/Until

[John Bugner]

In imperative OO languages, there are for/while loops:

A for-loop often looks like this:

for (i = 0; i < 100; i++) {
a[i] = f(i);
}

In Elm (and Haskell), we have the neat `map` function that captures this
pattern:

map f a

A while-loop looks like this:

while (!isDone(s)) {
f(s);
}

Haskell has the `until` function that captures this pattern:

until isDone f s

Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?

Anyways, it seems that somebody else already yearned for `until` like me,
and made this module:
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...

I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
this:

collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u

This function is elegantly defined, but not very useful, because the result
of every (positive) number will simply return 1 (mathematicians strongly
suspect so, anyways). What's interesting is the *sequence* that a number
makes on it's way down to 1. So I made a function that repeats like
`until`, but also records each intermediate result in a list, like `scanl`:

scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]

I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.

Anyways... answers, thoughts, and comments are welcome.

[art yerkes]

Lazy lists are a slightly more versatile way to do iteration in elm. They
can
iterate up to a certain index (like a for loop, using iterate and take).
And emulate
a while loop using
http://package.elm-lang.org/packages/elm-community/lazy-list/1.0.0/Lazy-List#takeWhile
.
Lazy list has toList and toArray functions that will fully evaluate a lazy
list that ends.

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like me,
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.

[Erkal Selman]

What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like me,
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.

[art yerkes]

You might need to do optimizations until there are no more changes to make.
Conceptually, you can express it as a while loop.

Post by Erkal Selman
What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like me,
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.

[Erkal Selman]

Ok, but that was not my question.

I will try to give a more general, theoretical answer. I hope that it makes
you gain more insight.

There are different models of computation, like Turing Machines.
One of them is, for example, the so-called *WHILE-language.* It is an
imperative language. There is no good Wikipedia entry for it, but you can
look at http://profs.sci.univr.it/~merro/files/WhileExtra_l.pdf
Another model of computation is the lambda-calculus, on top of which all
the functional programming languages are built.

Everything that you can do with one, you can do with the other.

If you think imperatively, you express it with "while ... do ...",
if you think declaratively, you express it via recursive definition.

While-loops in imperative languages and recursive function definitions in
functional languages are, in their essence, the same thing.

( You cannot simulate every while loop with things like List.map though.
See https://en.wikipedia.org/wiki/LOOP_(programming_language) )

Post by art yerkes
You might need to do optimizations until there are no more changes to
make. Conceptually, you can express it as a while loop.

Post by Erkal Selman
What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.

[art yerkes]

My response supposed that OP was trying to get his bearings in elm, and I
was responding to his scanUntil function with a slightly more idiomatic IMO
(if potentially a bit slower) use of takeWhile from LazyList. You can
simulate every while loop with lazy lists, given a way to generate values (
http://package.elm-lang.org/packages/TheSeamau5/elm-lazy-list/2.0.0/Lazy-List#iterate
) which we might as well call 'unfold' here, map (
http://package.elm-lang.org/packages/TheSeamau5/elm-lazy-list/2.0.0/Lazy-List#map
) and terminate (
http://package.elm-lang.org/packages/TheSeamau5/elm-lazy-list/2.0.0/Lazy-List#takeWhile
).

My intuition says the question might have been more practical than
theoretical, but there's IMO there's nothing wrong with asking it in this
way.

Demonstrating use of lazy in elm, I think the result can be easier to read
than explicit recursion:
import Lazy.List as LL exposing (LazyList)

lazyCollatz : Int -> LazyList Int
lazyCollatz n =
let c n = if n % 2 == 0 then n // 2 else 3 * n + 1 in
LL.iterate c n |> LL.takeWhile ((/=) 1)

main : Html a
main =
lazyCollatz 7 |> LL.toList |> toString |> text

Post by Erkal Selman
Ok, but that was not my question.
I will try to give a more general, theoretical answer. I hope that it
makes you gain more insight.
There are different models of computation, like Turing Machines.
One of them is, for example, the so-called *WHILE-language.* It is an
imperative language. There is no good Wikipedia entry for it, but you can
look at http://profs.sci.univr.it/~merro/files/WhileExtra_l.pdf
Another model of computation is the lambda-calculus, on top of which all
the functional programming languages are built.
Everything that you can do with one, you can do with the other.
If you think imperatively, you express it with "while ... do ...",
if you think declaratively, you express it via recursive definition.
While-loops in imperative languages and recursive function definitions in
functional languages are, in their essence, the same thing.
( You cannot simulate every while loop with things like List.map though.
See https://en.wikipedia.org/wiki/LOOP_(programming_language) )

Post by art yerkes
You might need to do optimizations until there are no more changes to
make. Conceptually, you can express it as a while loop.

Post by Erkal Selman
What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current
elmic way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like
me, and made this module: http://package.elm-lang.org/pa
ckages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from
Haskell's `(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a ->
a) -> a`. I'm not sure why. If he wanted to match the usual impOO order,
then why not `a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think
Haskell's order is the right order, because it let's you make useful
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelud
e.html#v:iterate ), but feels right because the most useful value is
probably going to be the last one calculated. But maybe this doesn't
matter, because if you really want the last one calculated, then you'd just
use `until` instead anyways.
Anyways... answers, thoughts, and comments are welcome.
--

You received this message because you are subscribed to a topic in the
Google Groups "Elm Discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/
topic/elm-discuss/Tv-vIRBNjeA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to
For more options, visit https://groups.google.com/d/optout.

[John Bugner]

For example, making a function that flood fills an area from a given start
point. You know that it'll eventually end, but you don't know exactly how
many times you need to recurse, unlike 'map' or 'fold', where the number of
times is the same as the number of items in the list/collection.

It's basically a wrapper for the recursion, letting your function focus on
the logic.

Post by Erkal Selman
What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like me,
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.

[Yosuke Torii]

Hi John,

I don't know the reason why Elm does not have them but Elm's core library
usually gives best minimum set of functions. For example, List module don't
have `find`, `zip`, and `scanl` that are included in community package
named list-extra
<http://package.elm-lang.org/packages/elm-community/list-extra/6.1.0/List-Extra>.
But I don't think all of them should always be listed in core, simply
because it is too many. So it should be important how often we use them or
how these functions effectively work in practice.

I agree that basically it is better to not write a bare recursion. I also
agree `until : (a -> Bool) -> (a -> a) -> a -> a` is better than `until
: (a -> Bool) -> a -> (a -> a) -> a`. But in my daily development,
generating a list or calculating until some condition is very rare logic. I
wonder which is easier to choose/remember a function or to write/read a
recursive function.

Post by John Bugner
For example, making a function that flood fills an area from a given start
point. You know that it'll eventually end, but you don't know exactly how
many times you need to recurse, unlike 'map' or 'fold', where the number of
times is the same as the number of items in the list/collection.
It's basically a wrapper for the recursion, letting your function focus on
the logic.

Post by Erkal Selman
What exactly do you need the while-loop for?

Post by John Bugner
for (i = 0; i < 100; i++) {
a[i] = f(i);
}
In Elm (and Haskell), we have the neat `map` function that captures this
map f a
while (!isDone(s)) {
f(s);
}
until isDone f s
Elm lacks this function. Is there a reason why? What's the current elmic
way of doing this? Explicit recursion, I assume?
Anyways, it seems that somebody else already yearned for `until` like
http://package.elm-lang.org/packages/Chadtech/elm-loop/1.0.2/Loop ...
I note though, that he changed the order of the arguments from Haskell's
`(a -> Bool) -> (a -> a) -> a -> a` to `(a -> Bool) -> a -> (a -> a) -> a`.
I'm not sure why. If he wanted to match the usual impOO order, then why not
`a -> (a -> Bool) -> (a -> a) -> a` instead ? Anyways, I think Haskell's
order is the right order, because it let's you make useful closures, like
collatz : Int -> Int
collatz =
let
u : Int -> Int
u n =
if isEven n
then n // 2
else 3 * n + 1
in
until ((==) 1) u
This function is elegantly defined, but not very useful, because the
result of every (positive) number will simply return 1 (mathematicians
strongly suspect so, anyways). What's interesting is the *sequence* that a
number makes on it's way down to 1. So I made a function that repeats like
scanUntil : (a -> Bool) -> (a -> a) -> a -> List a
scanUntil p u s =
let
p_ : List a -> Bool
p_ xs = case xs of
[] -> True
x :: _ -> p x
u_ : List a -> List a
u_ xs = case xs of
[] -> []
x :: _ -> u x :: xs
in
until p_ u_ [s]
I'm not sure that `scanUntil` is the best name. Can anybody think of a
better name? I also note that list that it returns is reversed compared to
`scanl`'s and Haskell's `iterate` function (
https://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:iterate
), but feels right because the most useful value is probably going to be
the last one calculated. But maybe this doesn't matter, because if you
really want the last one calculated, then you'd just use `until` instead
anyways.
Anyways... answers, thoughts, and comments are welcome.