Kata

Introduction

Infinite sequences are common, natural numbers for example are defined such that they always have a successor. In Haskell, most of the time lists are used to model infinite sequences, but why should we check for the empty case, if it will never occur?

Streams offer an elegant alternative to model infinite data. A stream has a head element and an infinite tail, in lazy languages this is no problem, since the tail gets only evaluated when needed. But in languages with strict evaluation we need a lambda function to delay evaluation.

data Stream a = S a (Stream a)

-- Note: We will define Stream with the equivalent infix operator constructor.
data Stream a = a :> Stream a

/*
    Unevaluated expressions in Haskell are called thunks. They are
    evaluated when needed, and all shared references then point to
    the evaluated data.

    In the Java version we use the Thunk class. This enables lazy sharing,
    through modification of the Thunk. Note that even though the usage of
    Thunk in itself is impure, the usage is pure as long as the passed Supplier
    is pure. (That is: The value generated by the supplier is always the same.)

    Basic usage of Thunk:
*/

// create from a value
Thunk<Integer> lazyA = Thunk.now(42);

// nothing is evaluated here
int a = lazyA.get();

// create from a supplier
Thunk<Integer> lazyB = Thunk.delay(() -> 21);

// create a new lazy computation with a function (the type of the thunk can change!)
Thunk<Integer> lazyC = lazyB.chain(x -> x * 2);

// evaluates lazyB and then lazyC
int c1 = lazyC.get();

// everything already evaluated here, since lazyC is shared!
int c2 = lazyC.get();

/*
    Unevaluated expressions in Haskell are called thunks. They are
    evaluated when needed, and all shared references then point to
    the evaluated data.

    In the JavaScript version we use the Thunk class. This enables lazy sharing,
    through modification of the Thunk. Note that even though the usage of
    Thunk in itself is impure, the usage is pure as long as the passed supplier function
    is pure. (That is: The value generated by the supplier is always the same.)

    Basic usage of Thunk:
*/

// create from a value
var lazyA = Thunk.now(42);

// nothing is evaluated here
var a = lazyA.get();

// create from a supplier (which is a nullary function)
var lazyB = Thunk.delay(() => 21);

// create a new lazy computation with a function (the type of the thunk can change!)
var lazyC = lazyB.chain(x => x * 2);

// evaluates lazyB and then lazyC
var c1 = lazyC.get();

// everything already evaluated here, since lazyC is shared!
var c2 = lazyC.get();

/*
    In C# the Lazy class is used to model delayed values.
*/

// A function is passed, but no Foo is created yet.
Lazy<Foo> lazyFoo = new Lazy<Foo>(() => new Foo());

// Accessing the Value property will evaluate the function and share the result.
Foo foo = lazyFoo.Value;

Basics

Write headS which returns the value at the head of the stream and tailS which drops the first value of the stream.

Let the streams flow!

Implement functions to construct streams:

• repeatS will repeat the same value over and over again.
• iterateS will repeatedly apply the same function to the result of the last iteration (starting with a given value).
• cycleS will repeat a list forever.
• fromS will count numbers upwards by one.
• fromStepS will count numbers with a given step width.

Modifying and reducing streams

To work with streams, we always have to write a computation which ends in finite time, therefore we can only inspect a finite part of the stream. Implement common functions:

• foldrS folds a stream with a function from the left (The resulting structure can also be infinite!).

-- Example: Add a zero before every element
intersperseZeroS = foldrS (\x r -> 0 :> x :> r)

/*
    A simple example which adds a 0 before every value in the stream.
    'r' is the unevaluated result of the recursive call to 'foldrS' on
    the tail of the stream, therefore a thunk.
*/
Stream.fromS(1).foldrS((x, r) => new Stream(0, Thunk.now(new Stream(x, r))));
// result: 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...

• filterS picks only those values, which satisfy the predicate.
• takeS takes a given number of elements from the stream.
• dropS drops a given number of elements from the stream. (Hint: Make sure to handle negative values.)
• Haskell only: splitAtS does take and drop at the same time.
• zipWithS merges 2 streams, by applying a function to each pair of values.
• Implement fmap, which maps every value of a stream with a function.
• Haskell only: Write an instance of Applicative for streams (type signatures are provided, in case you don't know what that means).

To infinity and beyond

With the written combinators, we can already do very useful things, for example we can write functions without relying on the unsafe head and tail functions for lists.

Write streams for the following sequences:

• fibS is the stream of all fibonacci numbers (starting with 0).
• primeS is the stream of all prime numbers.

Hint: The obvious definition of primeS would be with filterS and an isPrime predicate, while this sounds simple, it is not the most efficient solution (since it has to brute-force all numbers up to the given number). Figure out a way to reduce the amount of numbers to test in every step!