Lazy lists

Q&A's, tips, howto's
Post Reply
abbat
Posts: 8
Joined: Tue Nov 03, 2009 7:49 pm

Lazy lists

Post by abbat »

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

Code: Select all

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

itistoday
Posts: 413
Joined: Sun Dec 02, 2007 5:10 pm
Location: I'm sitting right next to you. :)
Contact:

Re: Lazy lists

Post by itistoday »

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

http://newlispfanclub.alh.net/forum/vie ... f=5&t=2162
Get your Objective newLISP groove on.

Lutz
Posts: 5279
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Lazy lists

Post by 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 all

(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 all

(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 all

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

Post Reply