So I felt this 0.16 tutorial
<https://www.classes.cs.uchicago.edu/archive/2015/winter/22300-1/lectures/TailRecursion.html>
helped me understand trampolines better. Then it took a bit of work
rewriting `create` in a way that utilized tail calls. But the new version
is still failing with "too much recursion." Adding or removing the
trampolines doesn't seem to make a difference.
Below is a SSCCE, with dummy implementations for wrap and partition. In
anybody has insight into what I am doing wrong, I would really appreciate
it!
module Main exposing (..)
import Html
import Dict exposing (Dict)
import Trampoline exposing (Trampoline)
main =
[1..4500] |> create |> toString |> Html.text
create : List Foo -> Tree
create foos =
Trampoline.evaluate (descend foos [])
type Partial
= LeftBranch Bar (List Foo)
| RightBranch Bar Tree
descend : List Foo -> List Partial -> Trampoline Tree
descend incomplete stack =
case incomplete of
[] ->
Trampoline.jump (\_ -> ascend (Leaf emptyFoo) stack)
foo :: [] ->
Trampoline.jump (\_ -> ascend (Leaf foo) stack)
_ ->
Trampoline.jump
(\_ ->
let
bar =
wrap incomplete
( left, right ) =
partition bar incomplete
in
descend left (LeftBranch bar right :: stack)
)
ascend : Tree -> List Partial -> Trampoline Tree
ascend complete stack =
case stack of
[] ->
Trampoline.done complete
(LeftBranch parent sibling) :: remainder ->
Trampoline.jump
(\_ ->
descend sibling (RightBranch parent complete ::
remainder)
)
(RightBranch parent sibling) :: remainder ->
Trampoline.jump
(\_ ->
ascend (Node parent sibling complete) remainder
)
type alias Bar =
String
type alias Foo =
Int
type Tree
= Leaf Foo
| Node Bar Tree Tree
wrap : List Foo -> Bar
wrap =
toString
partition : Bar -> List Foo -> ( List Foo, List Foo )
partition _ foos =
let
n =
List.length foos // 2
in
( List.take n foos, List.drop n foos )
emptyFoo : Foo
emptyFoo =
0
On Tue, Jul 12, 2016 at 10:08 AM, Max Goldstein <[email protected]>
wrote:
> Nah, trampoline takes some mental gymnastics! Hope it's helpful for your
> tree problem.
>
> --
> 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 [email protected].
> For more options, visit https://groups.google.com/d/optout.
>
--
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
