CODEWITHSUNDEEP
dynamic-programmingmemoizationelm
john mangual
john mangual

Reputation: 8172

memoization in Elm

I am trying to write a pseudo-random generator in Elm (to generate points on a screen) but not so easy since it interferes with the ``purity" of the Elm compiler.

OK, so why not write our own function? We can get sort-of random behavior if we write stuff like:

-- initial state
randomNumbers = [ 1 ]
x = 1
b = 2
n = 2017

-- generate random numbers
x = (x*b) % n
randomNumbers = x :: randomNumbers

This does not follow Elm's rule of variable assignments. Something is wrong.

All I am doing is finding the power of 2 mod 2017. The first few are easy but then the sequence gets unpredictible. So I need to keep track of the last number computed.

[ 1,  2,  4, 8, ... , 1024, 31, 62, 124, ...]

Even if I try to use special properties of arithmetic I still have to compute this sparse list of powers

[ 1, 2^1, 2^2, 2^4, 2^8, 2^16, ... ]

can I can solve by successive squaring, but I still need some way to memorize the last step.

I thought... as long as I write my own code, I don't have to import randomness from the "real world" to generate my fair numbers. This way respecting the pureness of Elm. However, I end up writing something that is stateful.

Elm does have a random-number generator now - an implementation of some algorithm - in the Random library, returning a generator type.

This repl session has been quite instructive:

> import Random exposing (..)
>
> initialSeed 0

Seed { 
    state = State 1 1 , 
    next =  <function>, 
    split = <function>, 
    range = <function> 
  }
    : Random.Seed

> seed0 = initialSeed 101

Seed { 
    state = State 102 1, , 
    next =  <function>, 
    split = <function>, 
    range = <function> 
  }
    : Random.Seed

> step ( int 0 10 ) seed0

(10,Seed { state = State 4081428 40692, , 
    next =  <function>, 
    split = <function>, 
    range = <function> 
  }
    : ( Int, Random.Seed )

Even with my simplified baby random number generator, what is so stateful here?

My apologies in advance if I say memoizaton when I mean dynamic programming or the other way around

What is the difference between memoization and dynamic programming?

If I could write a stateful function f that remembered things, I could generate all my values with just one line:

List.map f [1..100]

Upvotes: 2

Views: 807

Answers (1)

john mangual
john mangual

Reputation: 8172

two candidates:

A

https://github.com/elm-community/list-extra/blob/3.1.0/src/List/Extra.elm

iterate : (a -> Maybe a) -> a -> List a
iterate f x =
  case f x of
    Just x' -> x :: iterate f x'
    Nothing -> [x]

B

https://github.com/elm-community/elm-lazy-list/blob/1.3.0/src/Lazy/List.elm

{-| Create an infinite list of applications of a function on some value.
Equivalent to:
    x ::: f x ::: f (f x) ::: f (f (f x)) ::: ... -- etc...
-}

iterate : (a -> a) -> a -> LazyList a
iterate f a =
    lazy <|
        \() ->
            Cons a (iterate f (f a))

Upvotes: 1

Related Questions