Re: [elm-discuss] recursively generating a tree

[Ian Mackenzie]

Good to know!

By the way, is the original code you were working on part of an open-source 
library, by any chance? I'm working on some 2D/3D geometric libraries for 
Elm myself, including stuff like bounding boxes and spatial trees much like 
the one you describe. Might would be worth seeing if there are places we 
can collaborate (or at least not duplicate work if we don't need to). 

On Wednesday, 13 July 2016 07:15:21 UTC+10, Nick H wrote:
>
> Well, it turns out the bug isn't in my code. It is in elm-lang/core 
> .
>
> 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  > wrote:
>
>> So I felt this 0.16 tutorial 
>> 
>>  
>> 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 > > 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 elm-discuss...@googlegroups.com .
>>> 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 elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [elm-discuss] recursively generating a tree

[Max Goldstein]

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 elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [elm-discuss] recursively generating a tree

[Nick H]

*sigh* Never mind, I am being dumb.

factorial : Int -> Int
factorial x =
Trampoline.evaluate (fac 1 x)


fac : Int -> Int -> Trampoline Int
fac acc n =
if n <= 0 then
Trampoline.done acc
else
Trampoline.jump (\_ -> fac (n * acc) (n - 1))


On Tue, Jul 12, 2016 at 9:17 AM, Nick H  wrote:

> ... and I have no idea how this is supposed to work. Even for primitive
> recursion
>
> factorial : Int -> Int
> factorial x =
> Trampoline.evaluate (fac x)
>
>
> fac : Int -> Trampoline Int
> fac x =
> if x <= 0 then
> Trampoline.done 1
> else
> Trampoline.jump
> (\_ ->
> ???
> )
>
>
>
> On Tue, Jul 12, 2016 at 7:25 AM, Nick H  wrote:
>
>> Ian, that is a great thought, but even if we split the list exactly in
>> half, the call stack fills up when the list length gets to around 4500.
>>
>> partition _ list =
>>   let
>> n = List.length list // 2
>>   in
>> (List.take n list, List.drop n list)
>>
>> In my specific problem, the "wrap" function finds the smallest
>> rectangular prism that encloses a set of 3D points. The "partition"
>> function splits the list of points in half, with a plane that is aligned
>> with one of the box's axes. I have a lot of tests to ensure the function
>> doesn't break in weird cases, like all of the points being identical. So I
>> am pretty sure the partition is doing a reasonable split.
>>
>> I am taking a look at the trampoline library now...
>>
>> On Tue, Jul 12, 2016 at 12:03 AM, Janis Voigtländer <
>> janis.voigtlaen...@gmail.com> wrote:
>>
>>> Maybe the Trampoline library can help you?
>>>
>>> http://package.elm-lang.org/packages/elm-lang/trampoline/1.0.0/Trampoline
>>>
>>>
>>> Am Dienstag, 12. Juli 2016 schrieb Nick H :
>>>
 Here is a puzzle for you:

 For a large enough list, the code below will fill up the call stack and
 crash. It makes sense that the Elm compiler can't optimize it with tail
 calls, since the recursive function gets called more than once per
 iteration.

 What is the best way to rewrite this without using recursion?



 type Tree = Leaf Foo | Node Bar Tree Tree
>
> create : List Foo -> Tree
> create faces =
>   case faces of
> [] ->
>   dummyFoo
>
> foo :: [] ->
>   Leaf f
>
> list ->
>   let
> box = wrap list
>
> ( left, right ) = partition box list
>   in
> Node box (create left) (create right)
>
> wrap : List Foo -> Bar
>
> partition : Bar -> List Foo -> (List Foo, List Foo)
>
> --
 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 elm-discuss+unsubscr...@googlegroups.com.
 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 elm-discuss+unsubscr...@googlegroups.com.
>>> 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 elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [elm-discuss] recursively generating a tree

[Nick H]

... and I have no idea how this is supposed to work. Even for primitive
recursion

factorial : Int -> Int
factorial x =
Trampoline.evaluate (fac x)


fac : Int -> Trampoline Int
fac x =
if x <= 0 then
Trampoline.done 1
else
Trampoline.jump
(\_ ->
???
)



On Tue, Jul 12, 2016 at 7:25 AM, Nick H  wrote:

> Ian, that is a great thought, but even if we split the list exactly in
> half, the call stack fills up when the list length gets to around 4500.
>
> partition _ list =
>   let
> n = List.length list // 2
>   in
> (List.take n list, List.drop n list)
>
> In my specific problem, the "wrap" function finds the smallest rectangular
> prism that encloses a set of 3D points. The "partition" function splits the
> list of points in half, with a plane that is aligned with one of the box's
> axes. I have a lot of tests to ensure the function doesn't break in weird
> cases, like all of the points being identical. So I am pretty sure the
> partition is doing a reasonable split.
>
> I am taking a look at the trampoline library now...
>
> On Tue, Jul 12, 2016 at 12:03 AM, Janis Voigtländer <
> janis.voigtlaen...@gmail.com> wrote:
>
>> Maybe the Trampoline library can help you?
>>
>> http://package.elm-lang.org/packages/elm-lang/trampoline/1.0.0/Trampoline
>>
>>
>> Am Dienstag, 12. Juli 2016 schrieb Nick H :
>>
>>> Here is a puzzle for you:
>>>
>>> For a large enough list, the code below will fill up the call stack and
>>> crash. It makes sense that the Elm compiler can't optimize it with tail
>>> calls, since the recursive function gets called more than once per
>>> iteration.
>>>
>>> What is the best way to rewrite this without using recursion?
>>>
>>>
>>>
>>> type Tree = Leaf Foo | Node Bar Tree Tree

 create : List Foo -> Tree
 create faces =
   case faces of
 [] ->
   dummyFoo

 foo :: [] ->
   Leaf f

 list ->
   let
 box = wrap list

 ( left, right ) = partition box list
   in
 Node box (create left) (create right)

 wrap : List Foo -> Bar

 partition : Bar -> List Foo -> (List Foo, List Foo)

 --
>>> 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 elm-discuss+unsubscr...@googlegroups.com.
>>> 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 elm-discuss+unsubscr...@googlegroups.com.
>> 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 elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [elm-discuss] recursively generating a tree

[Nick H]

Ian, that is a great thought, but even if we split the list exactly in
half, the call stack fills up when the list length gets to around 4500.

partition _ list =
  let
n = List.length list // 2
  in
(List.take n list, List.drop n list)

In my specific problem, the "wrap" function finds the smallest rectangular
prism that encloses a set of 3D points. The "partition" function splits the
list of points in half, with a plane that is aligned with one of the box's
axes. I have a lot of tests to ensure the function doesn't break in weird
cases, like all of the points being identical. So I am pretty sure the
partition is doing a reasonable split.

I am taking a look at the trampoline library now...

On Tue, Jul 12, 2016 at 12:03 AM, Janis Voigtländer <
janis.voigtlaen...@gmail.com> wrote:

> Maybe the Trampoline library can help you?
>
> http://package.elm-lang.org/packages/elm-lang/trampoline/1.0.0/Trampoline
>
>
> Am Dienstag, 12. Juli 2016 schrieb Nick H :
>
>> Here is a puzzle for you:
>>
>> For a large enough list, the code below will fill up the call stack and
>> crash. It makes sense that the Elm compiler can't optimize it with tail
>> calls, since the recursive function gets called more than once per
>> iteration.
>>
>> What is the best way to rewrite this without using recursion?
>>
>>
>>
>> type Tree = Leaf Foo | Node Bar Tree Tree
>>>
>>> create : List Foo -> Tree
>>> create faces =
>>>   case faces of
>>> [] ->
>>>   dummyFoo
>>>
>>> foo :: [] ->
>>>   Leaf f
>>>
>>> list ->
>>>   let
>>> box = wrap list
>>>
>>> ( left, right ) = partition box list
>>>   in
>>> Node box (create left) (create right)
>>>
>>> wrap : List Foo -> Bar
>>>
>>> partition : Bar -> List Foo -> (List Foo, List Foo)
>>>
>>> --
>> 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 elm-discuss+unsubscr...@googlegroups.com.
>> 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 elm-discuss+unsubscr...@googlegroups.com.
> 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 elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.