Lazy lists

[abbat]

I want work in newLISP with lazy data structures like that:

Code Select Expand

(define fibs
    (lazy-cat '(0 1) (map + fibs (rest fibs))))
(fibs 10) ; ==> 55
How to do this?

[itistoday]

I explored this stuff a while ago, check it out:



http://newlispfanclub.alh.net/forum/viewtopic.php?f=5&t=2162">//http://newlispfanclub.alh.net/forum/viewtopic.php?f=5&t=2162

[Lutz]

newLISP has a different a method to write functions with state and write generators.



One method is using namespaces, the other is writing self-modifying code. Both demonstrated here writing a generator for fibonacci numbers:

Code Select Expand

(define (fibo:fibo)
    (if-not fibo:m
        (setq fibo:m '(0 1)))
    (pop (push (apply + fibo:m) fibo:m -1))
    (last fibo:m))

(fibo) ;=> 1
(fibo) ;=> 2
(fibo) ;=> 3
(fibo) ;=> 5
(fibo) ;=> 8


The self-modifying version is even shorter:

Code Select Expand

(define (fib)
    (pop (push (eval (last fib)) (last fib) -1) 1)
    (+ 0 1))

(fib) ;=> 2
(fib) ;=> 3
(fib) ;=> 5
(fib) ;=> 8

fib ;=> (lambda () (pop (push (eval (last fib)) (last fib) -1) 1) (+ 3 5))


The expression: (last fib) refers to the expression: (+ 0 1), which gets modified in place. Almost all destructive functions on newLISP can modify data in-place. The function 'setf' cannot.



The changed function can easily be serialzed to disk using: (save "fib.lsp" 'fib). Note that the same would be possible with the namespace function: (save "fibo.lsp" 'fibo). This feature is not available with closures, where the changed state of a function closure is hidden and not visible.



Last not least the memoizing function, which was mentioned in the thread again here, but used slighltly differently and a lot faster. This function generates a namespace for the target function and generates symbols for each call pattern to memorize results:

Code Select Expand

(define-macro (memoize mem-func func)
    (set (sym mem-func mem-func)
        (letex (f func  c mem-func)
          (lambda ()
              (or (context c (string (args)))
              (context c (string (args)) (apply f (args))))))))
             
(memoize fibonacci
    (lambda (n)
        (if(< n 2) 1
            (+  (fibonacci (- n 1))
                (fibonacci (- n 2))))))

(fibonacci 80) ;=> 37889062373143906


The function finishes in about 2ms on a 1.83 GHz Intel Core Duo 2 CPU. It would never finish, if not using memoization.