Skip to main content

ArrowLoop - finally seeing the light at the end of a long tunnel

Today I achieved something I long lusted to acheive, I made the step from fix to loop.
Basically by going from the applicative order Y combinator:

(define (y f)
((lambda (ff)
(lambda (xx)
(f (ff ff) xx)))
(lambda (ff)
(lambda (xx)
(f (ff ff) xx)))))

(define (fak f n)
(if (= 0 n)
(* (f (- n 1)) n)))

((y fak) 5)

to writing the same in lazy haskell:

y f = f $ y f

fak r 0 = 1
fak r n = n * r (n - 1)

-- ghci> y fak 5 ----> 120

someone told me that
 fix = y 

and that fix and loop are closely related.
I found an aspiring blogpost and thought it would be fun to
do the fibonacci recursion instead of the simple factorial.

That resulted in:

data SF a b = SF {runSF :: [a] -> [b]}

instance Arrow SF where
arr f = SF (map f)
(SF f) >>> (SF g) = SF (f >>> g)
first (SF f) = SF $ unzip >>> (first f) >>> zip'

instance ArrowLoop SF where
loop (SF f) = SF (\ins ->
let (outs, rs) = (zip' >>> f >>> unzip) (ins, lazy rs)
in outs)

lazy ~(z:zs) = z : lazy zs
zip' = uncurry zip
delay n = SF (n:)


The Fibonacci device
1 2 3 4

o----x ,->(delay b)-. ,-->(id)------->o
| |=>(uncurry (+))-|
o---------'---(id)-----' `-->(delay a)-->o

(the first input is merely a clock source...)

with the loop around:

fib n = take n (runSF (loop (fib' 0 1)) [1,1..])
fib' :: (Num a) => a -> a -> SF (a, a) (a, a)
fib' a b = arr snd >>> -- 1
(delay b &&& arr id) >>> -- 2
arr (uncurry (+)) >>> -- 3
(arr id &&& delay a) -- 4


The experimental Fibonacci device
1 2 3 4
o-------------------------------------------. ,------(id)----->o
,->(delay b)-. |===> (uncurry (*))-|
| |=>(uncurry (+))-----' `--->(delay a)-->o

fibex' :: (Num a) => a -> a -> SF (a, a) (a, a)
fibex' a b = (second
((delay b &&& arr id) >>> -- 1
arr (uncurry (+)))) -- 2
(arr (uncurry (*))) >>> -- 3
((arr id) &&& (delay a)) -- 4

fibex n = take n (runSF (loop (fib' 0 1)) [1..])

That was/is really fun. I like haskell.


Popular posts from this blog

Keys, Values and Rules: Three Important Shake Concepts

The title was a click-bait! This article will actually try to explain five instead of three important notions in Shake.

These are:
RulesKeysValuesThe Build DatabaseActions
This short blog post was inspired by the hurdles with my Shake based build, after the new Shake version was released, which had breaking API changes.

Jump to the next section if you are not interested in the why and how of this blog post.

Shake is rule based build system much like GNU make. Like make it is robust, unlike make, it is pretty fast and supports dynamic build dependencies.

But you knew all that already, if you are the target audience of this post, since this post is about me explaining to myself by explaining to you, how that build tool, I used for years, actually works.

Although I used it for years, I never read the paper or wrapped my head around it more than absolutely necessary to get the job done.

When Shake was updated to version 0.16.x, the internal API for custom rules was removed. Until then I w…

Lazy Evaluation(there be dragons and basement cats)

Lazy Evaluation and "undefined"
I am on the road to being a haskell programmer, and it still is a long way to go. Yesterday I had some nice guys from #haskell explain to me lazy evaluation.

Take a look at this code:

Prelude> let x = undefined in "hello world"
"hello world"

Because of Haskells lazyness, x will not be evaluated because it is not used, hence undefined will not be evaluated and no exception will occur.

The evaluation of "undefined" will result in a runtime exception:

Prelude> undefined
*** Exception: Prelude.undefined

Strictness means that the result of a function is undefined, if one of the arguments, the function is applied to, is undefined.
Classical programming languages are strict. The following example in Java will demonstrate this. When the programm is run, it will throw a RuntimeException, although the variable "evilX" is never actually used, strictness requires that all
arguments of a fu…

Erlang mock - erlymock

The project has evolved and can be found here: ErlyMock

Some features

Easy to use
Design based on easymock
Works together with otp: can be used even if the clut is called from another process, by invoking mock:verify_after_last_call(Mock,optional: timeout)
custom return functions
predefined return functions for returning values, receiving message, throwing exceptions, etc..
erlymock automatically purges all modules that were mocked, after verify()
Custom argument matchers:

%% Orderchecking types: in_order, out_of_order, stub;
%% Answering: {return, ...}|{error, ...}|{throw, ...}|{exit, ...}|{rec_msg, Pid}|{function, Fun(Args) -> RetVal}
expect(Mock, Type, Module, Function, Arguments, Answer = {AT, _}) when AT==return;AT==error;AT==throw;AT==exit;AT==rec_msg;AT==function ->
call(Mock, {expect, Type, Module, Function, length(Arguments), {Arguments, Answer}}).

%% this version of expect is suited for useing custom argument matchers
expect(Mock, Type, Module, Fun, …