Playing with streams in Julia

Delays and yields:

We need two definitions to make streams work. First, delay is a macro that replaces a function with an anonymous function with it's body equal to the function. Later when we need to evaluate the function, we only have to call the anonymous function. This is what yield does. Yield isn't as necessary, but it makes it clear what's happening.

In [1]:

macro delay(f)
    return quote
        # put the function inside a lambda
        function ()
            $f
        end
    end
end

In [2]:

function yield(delayed_function)
    delayed_function() # call it
end

Out[2]:

yield (generic function with 1 method)

In [3]:

something = @delay(println("text"))

Out[3]:

(anonymous function)

In [4]:

yield(something)

text

Making a stream type:

Now with that done we create a stream type. The first element is the actual value held there. The second element is a delayed stream constructor. We then create head and tail to access elements of the stream. Nth takes successive head and tails of a stream.

In [5]:

type IntStream
    literal
    next

    function IntStream(num)
        self = new()
        self.literal = num
        self.next = @delay(IntStream(num+1))
        return self
    end
end

In [6]:

function head(item::IntStream)
    return item.literal
end

Out[6]:

head (generic function with 1 method)

In [7]:

function tail(item::IntStream)
    return yield(item.next)
end

Out[7]:

tail (generic function with 1 method)

In [8]:

integers = IntStream(1)

Out[8]:

IntStream(1,(anonymous function))

In [9]:

head(integers)

Out[9]:

1

In [10]:

head(tail(tail(integers)))

Out[10]:

3

In [11]:

function nth(stream, n)
    if n == 1
        return head(stream)
    else
        return nth(tail(stream), n-1)
    end
end

Out[11]:

nth (generic function with 1 method)

In [12]:

nth(integers, 50)

Out[12]:

50

More general definitions:

For more general streams it is simple to add a next method for each object.

In [13]:

type Stream
    obj
    next
    
    function Stream(obj, next) # next is the method for generating the next object
        self = new()
        self.obj = obj
        self.next = @delay(Stream(next(obj), next))
        return self
    end
end

In [14]:

function head(item::Stream)
    return item.obj
end

Out[14]:

head (generic function with 2 methods)

In [15]:

function tail(item::Stream)
    return yield(item.next)
end

Out[15]:

tail (generic function with 2 methods)

In [16]:

function nth(stream, n)
    if n == 1
        return head(stream)
    else
        return nth(tail(stream), n-1)
    end
end

Out[16]:

nth (generic function with 1 method)

Fibonacci list stream:

Now to try it on the Fibonacci numbers. Instead of making each element the nth Fibonacci number we'll make it the list of the first n+1 Fibonacci numbers.

In [17]:

function next_fib_list(list)
    return [ list, (list[end] + list[end-1]) ]
end

Out[17]:

next_fib_list (generic function with 1 method)

In [18]:

fib_list = Stream([0, 1], next_fib_list)

Out[18]:

Stream([0,1],(anonymous function))

In [19]:

nth(fib_list, 5)

Out[19]:

6-element Array{Int64,1}:
 0
 1
 1
 2
 3
 5

In [20]:

nth(fib_list, 10)

Out[20]:

11-element Array{Int64,1}:
  0
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55

In [21]:

for idx = 1:15
    println(nth(fib_list, idx))
end

[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]
[0,1,1,2,3,5,8,13,21,34,55,89,144]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

It is also possible to memoize the function calls so that expensive operations aren't run more than once.