Well, it turns out the bug isn't in my code. It is in elm-lang/core
<https://github.com/elm-lang/core/issues/601>.
List.take fills ups the call stack all on its own:
main = [ 1 .. 5000 ] |> List.take 2500 |> toString |> Html.text
List.drop does not have this problem. If we redefine the partition function
solely in terms of List.drop, even the code in the OP works fine!
partition _ foos =
let
n = List.length foos // 2
in
( List.reverse foos |> List.drop (n+1) |> List.reverse, List.drop n
foos )
I am happy that I learned how to use trampolines though. Maybe it will come
in handy some day :-)
On Tue, Jul 12, 2016 at 11:17 AM, Nick H <[email protected]> wrote:
> 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.
