Randoms as LazyLists

[Rupert Smith]

I have a function that takes a random Generator and turns it into a LazyList. The reason for this is so that I can combine random streams together with other lazy streams that I have using the Lazy.List library.

The function uses the exposed Lazy.List.LazyListView type, which I would rather avoid if it makes sense to:

generate : Generator a -> Seed -> LazyList a

generate generator seed =

    let

        ( value, newSeed ) =

            Random.step generator seed

    in

        lazy <|

            \() ->

                Cons value (generate generator newSeed)

This version uses iterate on a (a, Seed) -> (a, Seed) function, but then requires a map on the tuple to extract just the random items:

generate2 : Generator a -> Seed -> LazyList a

generate2 generator seed =

    let

        firstValueSeed =

            Random.step generator seed

        step ( value, seed ) =

            Random.step generator seed

    in

        LL.iterate step firstValueSeed

            |> LL.map first

Is there some obvious way of doing this without the extra map operation? or perhaps that will compile down efficiently anyway.

Does there perhaps need to be a variation on the Lazy.List.cons constructor that takes a '() -> LazyList a' argument to allow the cons operation to be passed as a continuation?

Rupert

[Rupert Smith]

On Friday, November 10, 2017 at 4:45:54 PM UTC, Rupert Smith wrote:

The function uses the exposed Lazy.List.LazyListView type, which I would rather avoid if it makes sense to:

The documentation says:

"It is not recommended to work with this type directly. Try working solely with the provided functions in the package."

 

But I wonder, does this really make sense? Its not like this library is going to swap out that representation for another one at a later time is it? In which case exposing the type and working with it directly, which is needed for pattern matching anyway, is no different than working with say the List type directly.

 

[art yerkes]

I always interpreted the warning in the documentation as "Don't use the name LazyListView or the Nil and Cons constructors, instead using head, tail and headAndTail for most pattern matchng".  I think it makes sense not to use the internal representation given that Dict and Array change when better implementations arise.  Does any code elm code actually pattern match these instead of using the functions?  Always thought it was weird to have this type exposed at all.

[Rupert Smith]

On Saturday, November 11, 2017 at 6:33:34 PM UTC, art yerkes wrote:

I always interpreted the warning in the documentation as "Don't use the name LazyListView or the Nil and Cons constructors, instead using head, tail and headAndTail for most pattern matchng".  I think it makes sense not to use the internal representation given that Dict and Array change when better implementations arise.  Does any code elm code actually pattern match these instead of using the functions?  Always thought it was weird to have this type exposed at all.

I cannot use the 'cons' constructor though, as it is not lazy enough:

generate : Generator a -> Seed -> LazyList a
generate generator seed =
    let
        ( value, newSeed ) =
            Random.step generator seed
    in

        cons value (generate generator newSeed)

Runs out of stack space, as the recursive step is evaluated eagerly.

I think it is strange to expose a type but recommend not using it. Either a type is opaque and cannot be used directly, or exposed and it is perfectly ok to use it.

[art yerkes]

'iterate' is the right way to do what you're looking for.  No idea why they chose to expose that.

generate : Generator a -> Seed -> LazyList a

generate generator seed =

    let start = Random.step generator seed in

    LL.iterate

        (\(v,s) -> Random.step generator s)

        start

    |> LL.map Tuple.first

--
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/BM_ZmUk-vck/unsubscribe.
To unsubscribe from this group and all its topics, send an email to elm-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[GordonBGood]

The LazyList library as it exists is seriously flawed as it crashes for many cases for infinite length lazy lists, which is probably why there is that caution. Please see my extensive PR which fixes almost every function so they can handle infinite length lazy lists within the guidelines.

[Rupert Smith]

On Monday, November 13, 2017 at 5:49:32 PM UTC, art yerkes wrote:

'iterate' is the right way to do what you're looking for.  No idea why they chose to expose that.

generate : Generator a -> Seed -> LazyList a

generate generator seed =

    let start = Random.step generator seed in

    LL.iterate

        (\(v,s) -> Random.step generator s)

        start

    |> LL.map Tuple.first

Yes, this is the same code as I posted originally (generate2). It just seemed overkill to have to apply a 'map first' when it can be accomplished in a single pass using the Cons constructor.

[Rupert Smith]

On Monday, November 13, 2017 at 11:48:19 PM UTC, GordonBGood wrote:

The LazyList library as it exists is seriously flawed as it crashes for many cases for infinite length lazy lists, which is probably why there is that caution. Please see my extensive PR which fixes almost every function so they can handle infinite length lazy lists within the guidelines.

That is not so good, as infinite lists is much of the point of lazy lists. Lets ping the package maintainer and find out why your PR is just sitting there since February.

[W. Gordon Goodsman]

Looks like this version of lazy-list and even lazy itself have been depreciated, thus my PR is closed.

I also looks like the recommended non-memoizing version of lazy-list has the same memory leaks for very long (infinite) lists, and thus needs my PR applied to it.

The rational to depreciating these seems to be performance when applied to their limited use in tests and I see that, as I tried to make changes to Lazy that would improve its lack of performance when run on some JavaScript engines that handle internal functions calling functions very poorly.

However, I strongly disagree with removing these memoization versions of the libraries from the language, as just because they aren't needed for tests doesn't mean they are never needed. Noah has suggested that one can implement memoization themselves when needed, but hasn't explained how one can do that and remain referentially transparent and not use JavaScript without using Lazy, and if one does implement Lazy themselves, then the resulting code won't be accepted for libraries because it contains JavaScript.

This thread is probably not the place to discuss this, although it is going to affect the objective of the OP, but I don't know where it should be discussed since Noah has requested we don't discuss it on elm-dev.

I'll cease and desist about this if someone can show me how to write referentially transparent deferred memoization of the result of a function  call without using Lazy or JavaScript.

--

[Rupert Smith]

On Friday, November 17, 2017 at 1:25:02 PM UTC, GordonBGood wrote:

The rational to depreciating these seems to be performance when applied to their limited use in tests and I see that, as I tried to make changes to Lazy that would improve its lack of performance when run on some JavaScript engines that handle internal functions calling functions very poorly.

Gordon, it took me a bit of digging through various docs and updates on elm-dev to understand it, but... the rational for deprecating elm-core/lazy with memoization, is that it allowed recursive structures to be created on the heap, and all other ways in which that was possible have been eliminated. This is all described here:

https://gist.github.com/evancz/07436448b7d6c947f21742dab46d1218

It seems to be partly motivated by making garbage collection simpler - presumably with WebAssembly in mind. I honestly don't know much of a real advantage that is, but it seems that was the trade-off decision that has already been made.

[W. Gordon Goodsman]

Oh, I understand the rationale, but it limits the general usefulness of lazy lists, as certain types of problems need memoization, and without Lazy as it currently exists there is no way to accomplish it without JavaScript.

Just because the creators of the language don't see a need for it doesn't mean it doesn't exist.  Even for a lazy list of random numbers, no memoization means that new random numbers will be computed every time the list is scanned, meaning the lazy list won't appear to be static.

--

[N H]

Basically, the way things work in Elm is that things exist if people need them -- and can demonstrate the need. So far, there haven't been much need for memoization, outside of the render loop. In fact, the main place where lazy has been used at all has been for generating fuzzy values for elm-test. There, I benchmarked and proved that elm-test is faster _without_ memoization. If you can identify a _real_ problem that you have that needs implicit memoization at the function level (rather than the render level, which elm-lang/virtual-dom provides) then make a case for it.

--
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+unsubscribe@googlegroups.com.

[Mark Hamburg]

Example usage of laziness:

We have an expensive layout algorithm which depends both on the data being laid out and the view size. Whenever either of these changes, we need to re-run the layout algorithm but we would prefer to do the computation only when absolutely necessary and only once for any given set of parameters.

What keeps us from using lazy views for this is that the actual view instantiation optimizes based on the portion that is visible. If we used the view system to memoize the layout independent of the visible range then we couldn't introduce a dependency on the visible range below that point in the hierarchy.

Mark

P.S. Cyclic structures can be avoided by having the compiler perform a strongly connected component analysis (e.g., using Tarjan's algorithm) and disallowing any SCC's that include anything other than function definitions. In fact, not doing so likely leaves open other cyclic cases and hence getting rid of Lazy likely does not eliminate cycles and instead just narrows the cases for which Elm is suitable.

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.

[Rupert Smith]

On Monday, November 27, 2017 at 7:50:01 AM UTC, Mark Hamburg wrote:

P.S. Cyclic structures can be avoided by having the compiler perform a strongly connected component analysis (e.g., using Tarjan's algorithm) and disallowing any SCC's that include anything other than function definitions. In fact, not doing so likely leaves open other cyclic cases and hence getting rid of Lazy likely does not eliminate cycles and instead just narrows the cases for which Elm is suitable.

My hunch is that enough has been done to make cyclic structures impossible, but I have made no detailed analysis to support that. If all data structures are immutable, then references within them have to be created when the structure is first created. The first structure in a cycle to be created must contain a reference to another structure in the cycle, for a cycle to be formed, but as the other structures have not yet been created, this cannot be done.

I think you should post an example of building a cyclic structure here, if you think it can be done:

https://gist.github.com/evancz/07436448b7d6c947f21742dab46d1218

[Mark Hamburg]

That page already has an example built using the decoder APIs so unless something is changing to disallow the creation of such cyclic decoders, cycles remain. The lifting trick still has a cycle at the end — it has to given the desire to build something recursive —through the functions and variables even if it doesn't end up in some of the data structures.

Specifically, since the lifting is being done to prevent repeated allocations of the Random.andThen and we potentially need to pass through the Random.andThen logic multiple times, the node must lead back to itself.

Mark

--

[Rupert Smith]

On Monday, November 27, 2017 at 4:33:57 PM UTC, Mark Hamburg wrote:

That page already has an example built using the decoder APIs so unless something is changing to disallow the creation of such cyclic decoders, cycles remain. 

I'm looking at the page. I don't see a cyclic example built with the Decoder API. What am I missing?

[Mark Hamburg]

My bad. Cyclic generator not decoder. Recursive decoders have the same issues.

Mark

--

[Rupert Smith]

On Monday, November 27, 2017 at 9:06:38 PM UTC, Mark Hamburg wrote:

Recursive decoders have the same issues.

I'll see if I can get my head around that. I use recursive decoders to decode JSON into recursive types, but the values I output from this are not recursive. I did not realize it is possible to build a recursive value with decoders? Do you have an example?

These are mutually recursive types from a content model that I have been working with. If the server sends me some content with a list of relationships, and one of the relationships refers to the original content, I will end up with multiple copies of the original content in the structure decoded into Elm.

I need to use Decode.lazy to do this. Is that memoized? Is that how decoders can create recursive values? Other than that, I don't see how they could.

type Content =
    Content
    {
    slug : Maybe String
    , path : Maybe String
    , contentType : Maybe (ContentType)
    , model : ContentModel
    , relationships : Maybe (List Relationship)
    , container : Maybe (List Content)
    , id : Maybe String
    }


type Relationship =
    Relationship
    {
    subject : Maybe (Content)
    , predicate : Maybe PredicateType
    , object : Maybe (Content)
    , id : Maybe String
    }

[Rupert Smith]

On Thursday, November 30, 2017 at 10:29:42 AM UTC, Rupert Smith wrote:

I need to use Decode.lazy to do this. Is that memoized? Is that how decoders can create recursive values? Other than that, I don't see how they could.

Do you need to start with a recursive object in Javascript, then decode into Elm using Decode.lazy, to produce a recursive value in Elm?

Approximately:

var rec = { field : rec };

myapp.ports.myport.send(rec);

type Rec =

    Rec
    {
        field : Rec
    }


port myport : (Rec -> msg) -> Sub msg

But of course, that isn't going to compile as ports won't decode tagged union types, and you need a tagged union type to define a recursive type.

[Mark Hamburg]

If you have a recursive JSON structure to decode, then the decoder either needs to refer to itself (a cycle) or it needs to generate a new decoder on each recursive step.

Mark

--

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+unsubscribe@googlegroups.com.

[W. Gordon Goodsman]

I agree that for your application in testing where memoization is not required, your implementation is much faster. In fact, your new implementation of a lazy list without memoization isn't really a lazy list but rather a Co-Inductive Stream (CIS), where the use of a forcing function is actually a nop and unnecessary, and the next Stream function could be called directly.

I have used such CIS's effectively where memoization was not required and had associated cost.

However, it seems to me to be flawed thinking to eliminate memoization from the publically accessible libraries just because no one has yet used it.  There are classes of problems that are inefficient and unnecessarily repeat calculations without memoization.

For example, the Hamming numbers sequence can be produced elegantly using true memoized lazy lists in Haskell as:

hamming() = 1 : foldr [] [5,3,2] where

  u n s = r where

    r = merge s (map (n*) (1:r))

merge [] b = b

merge a@(x:xs) b@(y:ys)

  | x < y = x : merge xs b

  | otherwise = y : merge a ys

Using memoized lazy lists, this algorithm is almost as elegant and efficient in Elm as in Haskell, but using only CIS's makes it both time and space inefficient, with redundantly repeated calculations and the streams unable to be garbage collected due to the functions needing to retain back pointers into the streams all the way back to the beginning.

There are many similar examples in mathematics and perhaps in graphics applications.

It seems to me to be a mistake to limit the generality of the language libraries just because the authors don't see a use case. While it is true that many JavaScript engines (all except Microsoft Edge) limit the efficiency of how memoization must be implemented for Elm (a function generating a function), this won't always necessarily be true, and almost certainly won't be true if and when Elm generates wasm code, now supported by all major browsers.

CIS's are easy enough to generate that they could be defined where needed as for the testing case, or could be a separate library.

Meanwhile the memoized Lazy type library really is needed, else there is no way to implement memoization without custom JavaScript, which is frowned upon.

[Rupert Smith]

On Tuesday, December 5, 2017 at 5:16:22 PM UTC, Mark Hamburg wrote:

If you have a recursive JSON structure to decode, then the decoder either needs to refer to itself (a cycle) or it needs to generate a new decoder on each recursive step.

There is a difference between a function that is recursive and values on the heap that are cyclic. The recursive functions issue seems to be with what order to output compiled javascript code in, when there are mutually recursive functions, as one may not be defined at the point in time when another needs to access it. The cyclic structures on the heap issue, is to do with how to make garbage collection very easy in a language that does not need cyclic structures.

I think this page is confusing because it discusses both issues at the same time:
https://gist.github.com/evancz/07436448b7d6c947f21742dab46d1218

[Mark Hamburg]

Functions are also heap allocated objects and reference other objects — e.g., decoders — just like other objects do.

Mark

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

[Rupert Smith]

On Friday, December 8, 2017 at 5:55:36 AM UTC, Mark Hamburg wrote:

Functions are also heap allocated objects and reference other objects — e.g., decoders — just like other objects do.

But presumably functions do not get garbage collected?

[Rupert Smith]

On Wednesday, December 6, 2017 at 2:38:09 AM UTC, GordonBGood wrote:

Meanwhile the memoized Lazy type library really is needed, else there is no way to implement memoization without custom JavaScript, which is frowned upon.

I think you make a good case for keeping it in Gordon. When I started this thread, all I really needed is a CIS for random numbers, but I can see that true lazy lists have their uses. Is it really worth throwing them out to make garbage collection by reference counting only possible if/when Elm is ported to web assembly?

[Mark Hamburg]

Functions get garbage collected. Otherwise think what would happen every time you use partial function application or define a function within a let or other nested context. Because those functions (can) capture values, they are new values just as much as a list or record or other data value would be.

Mark

--

[Mark Hamburg]

Now if you narrow it to a module scope function and a module scope decoder or generator, then no they won't get collected anymore than anything else at module scope and hence the reference cycle is immaterial to the GC. But that argument would apply just as well to a cyclic list at module scope.

Mark

[Rupert Smith]

On Saturday, December 9, 2017 at 2:13:18 AM UTC, Mark Hamburg wrote:

Functions get garbage collected. Otherwise think what would happen every time you use partial function application or define a function within a let or other nested context. Because those functions (can) capture values, they are new values just as much as a list or record or other data value would be.

Is this something that is specific to the way javascript works? In my experience partial function applications create a continuation, which is a stack frame holding the captured values. Once the function completes the stack frame is discarded, so there is no allocation or GC on the heap. Is this not how Elm would be implemented on webasm and managing its own memory?

[Mark Hamburg]

One can return a partial function application and it looks just like any other function, so in the general case, it can't be garbage collected. This isn't special to JavaScript. In fact, JavaScript doesn't support partial function application. What JavaScript, Elm, and pretty much any other language that purports to be functional does support is capturing values through closure creation and because those closures can be returned as values, they need to be subject to garbage collection.

Mark

--

[Rupert Smith]

On Saturday, December 16, 2017 at 9:27:28 PM UTC, Mark Hamburg wrote:

One can return a partial function application and it looks just like any other function, so in the general case, it can't be garbage collected. This isn't special to JavaScript. In fact, JavaScript doesn't support partial function application. What JavaScript, Elm, and pretty much any other language that purports to be functional does support is capturing values through closure creation and because those closures can be returned as values, they need to be subject to garbage collection.

Thanks for this explanation, I get it now. I will try and work out an example of how the mutually recursive functions can create a cyclic structure on the heap, based on this.