Thoughts and Code

FP Hacker Wanted

PALLADIN — Fri, 02 Sep 2011 03:44:00 GMT

H ομάδα μου και εγώ προσωπικά αναζητούμε F# hacker. Για περισσότερες πληροφορίες στείλτε μου PM.

"Είμαστε μια μικρή ομάδα έμπειρων F# προγραμματιστών και αναζητούμε νεαρό ταλαντούχο hacker

για να δουλέψει μαζί μας σε ένα πολύ ενδιαφέρον και φιλόδοξο F# based cloud programming framework-runtime (M-Brace).

Αν και οι γνώσεις γύρω από F# και .Net δεν είναι απαραίτητες, απαιτείται τουλάχιστον καλή γνώση και εμπειρία σε κάποια functional γλώσσα

(Lisp family, ML family, Haskell, Erlang, FP Scala) καθώς και πάθος-όρεξη για applied functional programming.

Για περισσότερες πληροφορίες και για αποστολή βιογραφικών nessos@nessos.gr"

F# in the Enterprise

PALLADIN — Fri, 04 Mar 2011 01:37:00 GMT

Αργά αλλα σταθερά η F# δείχνει την δύναμη της και εδραιώνεται στις συνειδήσεις των .Net προγραμματιστών.

Μετά και την ανακοίνωση του Async support στις vNext (C#, Vb) είναι ξεκάθαρο ότι η F# επηρεάζει και ξεχωρίζει.

Στο παρακάτω link όσοι ενδιαφέρονται μπορούν να δουν και το enterprise πρόσωπο της F#.

http://msdn.microsoft.com/en-us/fsharp/gg634701

Lazy but Fast

PALLADIN — Fri, 07 Jan 2011 02:10:00 GMT

Πολλές φορες έχω κάποιο αναδρομικό αλγόριθμο (p.x traversal ενός tree) και θέλω να τον εκτελέσω lazy.

Δυστυχώς και σε F# (seq) και σε C# (iterators), οι αλγόριθμοι καταλήγουν σε quadratic time και πολλές φορες σε stack-overflows.

Κουρασμένος από αυτή την κατάσταση, κατέληξα στο κάτωθι.

open System.Collections
open System.Collections.Generic

// LazyList dataType + Monoid Structure
type LazyList<'T> =   Empty
                    | Cons of 'T * (unit -> LazyList<'T>)
                    | Delay of (unit -> LazyList<'T>)
                    | Combine of LazyList<'T> * LazyList<'T> with
        interface IEnumerable<'T> with
            member self.GetEnumerator() =
                // tail-recursive enumeration 
                let rec toSeq stack = 
                    match stack with
                    | [] -> Seq.empty
                    | head :: tail ->
                        match head with
                        | Empty -> toSeq tail
                        | Cons (value, rest) -> seq { yield value; yield! toSeq <| rest () :: tail }
                        | Delay f -> toSeq <| f () :: tail
                        | Combine (first, second) -> toSeq <| first :: second :: tail
                (toSeq [self]).GetEnumerator() 
        interface IEnumerable with 
            member self.GetEnumerator() = (self :> IEnumerable<'T>).GetEnumerator() :> _ 

// Monoid Comprehension
type LazyListBuilder() = 
    member self.Yield value = Cons (value, fun () -> Empty)
    member self.YieldFrom value = value
    member self.Combine(first, second) = Combine (first, second) 
    member self.Delay f = Delay f
    member self.Zero() = Empty

let lazyList = new LazyListBuilder()


// Example
#time
type Tree<'T> = Empty | Branch of 'T * Tree<'T> * Tree<'T>

let rec createBalancedTree n = 
    if n <= 0 then Empty
    else Branch (n, createBalancedTree (n - 1), createBalancedTree (n - 1))

let rec createLeftSpinedTree n acc = 
    if n <= 0 then acc
    else createLeftSpinedTree (n - 1) (Branch (n, acc, Empty))

let tree = createBalancedTree 20
let leftSpinedTree = createLeftSpinedTree 100000 Empty

// Seq test
let rec flattenToSeq tree =
    match tree with
    | Empty -> Seq.empty
    | Branch (value, left, right) -> 
        seq { yield value; yield! flattenToSeq left; yield! flattenToSeq right }

tree
|> flattenToSeq
|> Seq.length 

leftSpinedTree
|> flattenToSeq
|> Seq.length 

// LazyList test
let rec flattenToLazyList tree =
    match tree with
    | Empty -> LazyList.Empty 
    | Branch (value, left, right) -> 
        lazyList { yield value; yield! flattenToLazyList left; yield! flattenToLazyList right }

tree
|> flattenToLazyList
|> Seq.length 

leftSpinedTree
|> flattenToLazyList
|> Seq.length

'M'agic & LINQ - IT PRO DEV CONNECTIONS

PALLADIN — Sat, 11 Dec 2010 01:44:00 GMT

Αν και καθυστερημένα... θα ήθελα να ευχαριστήσω όλους τους φίλους για την παρουσία τους και τα πολύ καλά τους λόγια.

Αν και η παρουσίαση ήταν κυρίως βασισμένη σε live hacking...

προσπάθησα να σπάσω σε βήματα το refactoring για όποιον θέλει να μελετήσει τον κώδικα.

Hughes's list in F#

PALLADIN — Sun, 14 Nov 2010 04:24:00 GMT

Ορίζοντας τις Combine και Zero σε ένα Computation expression μπορούμε να έχουμε Monoid comprehensions.

Πρόσφατα παρατήρησα ότι το Monadic Append στα γνωστά (Array, List, Seq) είναι σχετικά αργό.

#time
[ for i in {1..1000000} do
        yield i * 2; yield i * 3; yield i * 4; yield i * 5 ]
 
[| for i in {1..1000000} do
        yield i * 2; yield i * 3; yield i * 4; yield i * 5 |]
 
 
seq { for i in {1..1000000} do
        yield i * 2; yield i * 3; yield i * 4; yield i * 5 } |> Seq.iter ignore

Μια τεχνική για να έχουμε γρήγορο list append είναι να αξιοποιήσουμε μια παλαιά ιδέα από έναν guru.

type FuncList<'a> = 'a list -> 'a list

type FuncListBuilder() =
    member self.Combine (first : FuncList<'a>, second : FuncList<'a>) : FuncList<'a>  = (first << second) 
    member self.Zero() : FuncList<'a> = id
    member self.Yield (value : 'a) : FuncList<'a> = fun tail -> value :: tail
    member self.YieldFrom (value : FuncList<'a>) : FuncList<'a> = value
    member self.For (list : FuncList<'a>, f : 'a -> FuncList<'b>) : FuncList<'b> =
        fun tail -> [] |> list |> List.map f |> List.fold (fun acc value -> self.Combine(acc, value)) (self.Zero()) <| tail
    member self.Delay ( f : unit -> FuncList<'a>) : FuncList<'a> = f ()
 
let funcList = new FuncListBuilder()
let toFuncList (list : 'a list) : FuncList<'a> = list |> List.fold (fun acc value -> funcList { yield! acc; yield value }) id


 
[] |> funcList  { for i in toFuncList [1..1000000] do
                    yield i * 2; yield i * 3; yield i * 4; yield i * 5 }

Για περισσότερες πληροφορίες: http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf

Looking for Hacker

PALLADIN — Mon, 25 Oct 2010 21:50:00 GMT

H ομάδα μου και εγώ προσωπικά αναζητούμε F# hacker. Για περισσότερες πληροφορίες στείλτε μου PM.

"Είμαστε μια μικρή ομάδα έμπειρων F# προγραμματιστών και αναζητούμε νεαρό ταλαντούχο hacker για να δουλέψει μαζί μας σε ένα πολύ ενδιαφέρον και φιλόδοξο F# project. Αν και οι γνώσεις γύρω από F# και .Net δεν είναι απαραίτητες, απαιτείται τουλάχιστον σχετική εμπειρία σε κάποια functional γλώσσα (FP C#, FP Javascript, Lisp family, ML family, Haskell, Erlang) καθώς και όρεξη και πάθος για applied functional programming.

Για περισσότερες πληροφορίες και για αποστολή βιογραφικών nessos@nessos.gr"

Steps in Scala

PALLADIN — Wed, 13 Oct 2010 07:15:00 GMT

Θα ήθελα να δώσω πολλά μπράβο στους συγγραφείς του Steps Scala (Λοβέρδος, Συρόπουλος) για το θεωρητικό content που συμπεριέλαβαν.

Ιδιαίτερη μνεία πρέπει να γίνει για τo κεφαλαιο "Higher Order Polymorphism", που ασχολείται με τις ιδέες

του κλασικού πλέον Banana paper.

Έχοντας διαβάσει σχεδόν όλα τα βιβλία που έχουν βγει για Scala, μπορώ να πω με σιγουριά ότι το συγκεκριμένο βιβλίο ξεχωρίζει.

Monadic Retry

PALLADIN — Mon, 11 Oct 2010 01:41:00 GMT

Πολλές φορες έχουμε σενάρια που θα θέλαμε να εφαρμοσουμε συγκεκριμενα retry policies σε error prone computations.

Τα σενάρια αυτά εμφανίζονται αρκετά συχνά και κυρίως σε cloud computations.

Στο Azure για παράδειγμα, υπάρχουν και συγκεκριμένα APIs που παίζουν με Retry Policies.

Το παρακάτω monad είναι μια έμπνευση που είχα στο να κάνω combine το

reader monad (για το propagation του policy) μαζί με το exception monad έτσι ώστε να δομήσω ένα retry monad.

open System
open System.Threading
 
type ShouldRetry = ShouldRetry of (RetryCount * LastException -> bool * RetryDelay)
and RetryCount = int
and LastException = exn
and RetryDelay = TimeSpan
type RetryPolicy = RetryPolicy of ShouldRetry
   
type RetryPolicies() =
    static member NoRetry () : RetryPolicy =
        RetryPolicy( ShouldRetry (fun (retryCount, _) -> (retryCount < 1, TimeSpan.Zero)) )
    static member Retry (currentRetryCount : int , intervalBewteenRetries : RetryDelay) : RetryPolicy =
        RetryPolicy( ShouldRetry (fun (retryCount, _) -> (currentRetryCount < retryCount, intervalBewteenRetries)))
    static member Retry (currentRetryCount : int) : RetryPolicy =
        RetryPolicies.Retry(currentRetryCount, TimeSpan.Zero)
 
type RetryResult<'a> =
    | RetrySuccess of 'a
    | RetryFailure of exn
   
// Reader + Exception Monad DataType
type Retry<'a> = Retry of (RetryPolicy -> RetryResult<'a>)
 
type RetryBuilder() =
    member self.Return (value : 'a) : Retry<'a> = Retry (fun retryPolicy -> RetrySuccess value)
 
    member self.Bind (retry : Retry<'a>, bindFunc : 'a -> Retry<'b>) : Retry<'b> =
        Retry (fun retryPolicy ->
            let (Retry retryFunc) = retry
            match retryFunc retryPolicy with
            | RetrySuccess value ->
                let (Retry retryFunc') = bindFunc value
                retryFunc' retryPolicy
            | RetryFailure exn -> RetryFailure exn )
 
    member self.Delay (f : unit -> Retry<'a>) : Retry<'a> =
        Retry (fun retryPolicy ->
            let mutable resultCell : option<RetryResult<'a>> = None
            let mutable lastExceptionCell : exn = null
            let (RetryPolicy(ShouldRetry shouldRetry)) = retryPolicy
            let mutable canRetryCell : bool = true
            let mutable currentRetryCountCell : int = 0
            while canRetryCell do
                try
                    let (Retry retryFunc) = f ()
                    let result = retryFunc retryPolicy
                    resultCell <- Some result
                    canRetryCell <- false
                with e ->
                    lastExceptionCell <- e
                    currentRetryCountCell <- 1 + currentRetryCountCell
                    match shouldRetry(currentRetryCountCell, lastExceptionCell) with
                    | (true, retryDelay) ->
                        canRetryCell <- true
                        Thread.Sleep(retryDelay)
                    | (false, _) -> canRetryCell <- false
 
            match resultCell with
            | Some result -> result
            | None -> RetryFailure lastExceptionCell )
 
[<AutoOpen>]
module Retry =
    let retry = new RetryBuilder()
    // override default policy
    let retryWithPolicy (retryPolicy : RetryPolicy) (retry : Retry<'a>) =
        Retry (fun _ -> let (Retry retryFunc) = retry in retryFunc retryPolicy)

    let run (retry : Retry<'a>) (retryPolicy : RetryPolicy) : RetryResult<'a> =
        let (Retry retryFunc) = retry
        retryFunc retryPolicy

// DivByzero example
let rnd = System.Random()
let example = 
    retry {
        let! a = retry { return 1 / rnd.Next(0, 2) }
        let! b = retry { return 2 / rnd.Next(0, 2) }
        // override default policy
        let! c = retryWithPolicy (RetryPolicies.NoRetry()) (retry { return 3 / rnd.Next(0, 2) })

        return a * b * c
    }

run example (RetryPolicies.Retry 1)

Monadic Memoization in F# (The Continuation)

PALLADIN — Mon, 06 Sep 2010 04:13:00 GMT

Συνεχίζοντας τις περιπέτειες μου στον χώρο του monadic memoization, αποφάσισα να

εμπλουτίσω την προηγουμενη προσπάθειά μου με το Continuation Monad, έτσι ώστε να έχω tail calls και να αποφύγω "περίεργα" stack overflows.

Η ιδέα είναι να συνδυάσω το State Monad με το Continuation Monad (StateT Monad Transformer) και ως "δια μαγείας" όλα να δουλέψουν.

type StateContMonad<'s, 'a, 'r> = StateContMonad of ('s -> ('s -> 'a -> 'r) -> 'r)
type StateContBuilder() =
    member self.Return value = StateContMonad (fun state k -> k state value)
    member self.Bind(StateContMonad contStateMonad, f) = StateContMonad (fun state k -> contStateMonad state (fun state' value -> let (StateContMonad contMonad') = f value in contMonad' state' k))
    member self.Delay( f : unit -> StateContMonad<'s, 'a, 'r> ) = StateContMonad (fun state k -> let (StateContMonad contStateMonad) = f () in contStateMonad state k)
 
let memo = new StateContBuilder()
 
// val Y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
let rec Y f value = f (Y f) value
 
// val check : 'a -> StateContMonad<Map<'a,'r>,'r option,'r> when 'a : comparison
let check (value : 'a) : StateContMonad<Map<'a, 'r>, option<'r>, 'r> = StateContMonad (fun map k -> k map (Map.tryFind value map))
// val store : 'a * 'r -> StateContMonad<Map<'a,'r>,unit,'r> when 'a : comparison
let store (argument : 'a, result : 'r) : StateContMonad<Map<'a, 'r>, unit, 'r> = StateContMonad (fun map k -> k (Map.add argument result map) ())
 
// val memoize : ('a -> StateContMonad<Map<'a,'b>,'b,'b>) -> 'a -> StateContMonad<Map<'a,'b>,'b,'b> when 'a : comparison
let memoize f argument =
    memo {
        let! checkResult = check argument
        match checkResult with
        | Some result -> return result
        | None ->
            let! result = f argument
            do! store (argument, result)
            return result
    }
 
// val execute : (('a -> StateContMonad<Map<'a,'b>,'b,'b>) -> 'a -> StateContMonad<Map<'a,'b>,'b,'b>) -> 'a -> 'b when 'a : comparison
let execute f n = let (StateContMonad contStateMonad) = Y (memoize << f) n in contStateMonad Map.empty (fun _ value -> value)
 
// val big : int -> BigInteger
let big (value : int) = new System.Numerics.BigInteger(value)
 
// val fib : (BigInteger -> StateContMonad<'a,BigInteger,'b>) -> BigInteger -> StateContMonad<'a,BigInteger,'b>
let fib f n =
    if n = big 0 then memo { return big 0 }
    elif n = big 1 then memo { return big 1 }
    else
        memo {
            let! nMinus1Fib = f (n - big 1)
            let! nMinus2Fib = f (n - big 2)
            return nMinus1Fib + nMinus2Fib
        }
 
execute fib (big 100000)

Monadic Memoization in F#

PALLADIN — Tue, 17 Aug 2010 05:38:00 GMT

Πρόσφατα χρειάστηκε να χρησιμοποιήσω μια memoization συνάρτηση για ένα πρόβλημα δυναμικού προγραμματισμού.

Υλοποιώντας την κλασσική τεχνική χρειαζόμαστε μια συνάρτηση σαν την παρακάτω:

let memoize f = 
	let cache = new Dictionary<_, _>()	
	(fun x -> match cache.TryGetValue(x) with
                  | true, y -> y
	          | _       -> let v = f(x)
                                       cache.Add(x, v)
                                       v)

Το πρόβλημα με την παραπάνω συνάρτηση είναι ότι χρειαζόμαστε "κριμένα" side effects.

Μετά από μελέτη κατέληξα ότι η pure functional λύση θα περιελάμβανε τον Y combinator και το State Monad.

Η κεντρική ιδέα είναι να μετατρέψουμε μια συνάρτηση από a -> b σε a -> m b,

plus ότι χρειαζόμαστε να κάνουμε abstract και τις αναδρομικές κλήσεις για να εισάγουμε τους ελεγχους στα arguments.

My F# solution:

type StateMonad<'a, 's> = StateMonad of ('s -> ('a * 's))
 
type StateBuilder() =
    member self.Return value = StateMonad (fun state -> (value, state))
    member self.Bind (StateMonad stateMonad, f) = StateMonad (fun state -> let value, state' = stateMonad state in let (StateMonad stateMonad') = f value in stateMonad' state')
 
let memo = new StateBuilder()
 
// val Y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
let rec Y f value = f (Y f) value
 
// val check : 'a -> StateMonad<'r option,Map<'a,'r>> when 'a : comparison
let check (value : 'a) : StateMonad<option<'r>, Map<'a, 'r>> = StateMonad (fun map -> (Map.tryFind value map, map))
// val store : 'a * 'r -> StateMonad<unit,Map<'a,'r>> when 'a : comparison
let store (argument : 'a, result : 'r) : StateMonad<unit, Map<'a, 'r>> = StateMonad (fun map -> ((), Map.add argument result map))
 
// val memoize :('a -> StateMonad<'b,Map<'a,'b>>) -> 'a -> StateMonad<'b,Map<'a,'b>> when 'a : comparison
let memoize f argument =
    memo {
        let! checkResult = check argument
        match checkResult with
        | Some result -> return result
        | None ->
            let! result = f argument
            do! store (argument, result)
            return result
    }
 
// val execute : (('a -> StateMonad<'b,Map<'a,'b>>) -> 'a -> StateMonad<'b,Map<'a,'b>>) -> 'a -> 'b when 'a : comparison
let execute f n = let (StateMonad stateMonad) = Y (memoize << f) n in fst (stateMonad Map.empty)
 
// val fib : (int -> StateMonad<int,'a>) -> int -> StateMonad<int,'a>
let fib f n =
    if n = 0 then memo { return 0 }
    elif n = 1 then memo { return 1 }
    else
        memo {
            let! nMinus1Fib = f (n - 1)
            let! nMinus2Fib = f (n - 2)
            return nMinus1Fib + nMinus2Fib
        }
   
execute fib 1000

References:

http://www.cs.utexas.edu/~wcook/Drafts/2006/MemoMixins.pdf

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.3065

Clojure's Atoms in F#

PALLADIN — Mon, 12 Jul 2010 02:49:00 GMT

Μελετώντας την Clojure, την προσοχή μου τράβηξε ένα απλό αλλά πολύ χρήσιμο construct, το Atom.

Το Atom φαίνεται να είναι το πάντρεμα των ref cells της ML με lock free CAS concurrency semantics.

Επειδή τέτοια constructs είναι πολύ χρήσιμα στην F#, σκέφτηκα να υλοποιήσω κάτι ανάλογο.

My attempt:

type Atom<'a when 'a : not struct>(value : 'a) =
    let refCell = ref value
    
    let rec swap f = 
        let currentValue = !refCell
        let result = Interlocked.CompareExchange<'a>(refCell, f currentValue, currentValue)
        if obj.ReferenceEquals(result, currentValue) then ()
        else Thread.SpinWait 20; swap f
        
    member self.Value with get() = !refCell
    member self.Swap (f : 'a -> 'a) = swap f
        
    

let atom value = 
    new Atom<_>(value)
    
let (!) (atom : Atom<_>) =  
    atom.Value
    
let swap (atom : Atom<_>) (f : _ -> _) =
    atom.Swap f

Και ως παράδειγμα χρήσης, σκέφτηκα έναν απλό multithreaded counter.

(Σημείωση: βάζω το int μέσα στο lambda επειδή πρέπει να δώσω στο Atom ένα reference type)

let counter = atom (fun () -> 0)

let listOfIncrementAsync = [ for _ in [1..1000000] -> async { swap counter (fun f -> (fun result () -> result + 1) <| f()) } ]

listOfIncrementAsync |> Async.Parallel |> Async.Run |> ignore 

printfn "%d" ((!counter)()) //1000000

F# is out there

PALLADIN — Mon, 14 Jun 2010 01:59:00 GMT

Εδώ και πολλά χρονια ονειρευόμουν την μέρα που κάποια απόγονος της ML θα καταφέρει να σπάσει τα ακαδημαϊκά δεσμά της και να αποκτήσει μια ευρύτερη πιο γενική αντιμετώπιση.

Το όνειρο αυτό έγινε πραγματικότητα (υπό μια έννοια)!!!

Η F# είναι πλέον γεγονός και βρίσκεται εγκατεστημένη με κάθε VS 2010.

Ήδη στην εταιρία μου, κλείνουμε μια εβδομάδα λειτουργίας ενός απαιτητικού production server που τρέχει mission critical components γραμμένα σε F#.

Όσοι φίλοι αισθάνονται ότι πρέπει να υπάρχει κάτι περισσότερο από τα συνηθισμένα "{};++", τότε μπορούν να δώσουν μια ευκαιρία σε κάτι διαφορετικό.

Μετά από ένα σημείο θα αρχίσουν να βλέπουν τον κώδικα με άλλα μάτια... Σαν τον Neo στο τέλος του πρώτου Matrix .

Resources:

Use case:

http://www.microsoft.com/casestudies/case_study_detail.aspx?casestudyid=4000005226

Lectures: (Όσοι φίλοι παρακολουθήσουν τα μαθήματα και έχουν ερωτήσεις - απορίες, μπορούν να μου στείλουν ένα μήνυμα και θα είναι πραγματικά χαρά μου να βοηθήσω)

http://channel9.msdn.com/shows/Going+Deep/C9-Lectures-Dr-Don-Syme-Introduction-to-F-1-of-3/

http://channel9.msdn.com/shows/Going+Deep/C9-Lectures-Dr-Don-Syme-Introduction-to-F-2-of-3/

http://channel9.msdn.com/shows/Going+Deep/C9-Lectures-Dr-Don-Syme-Introduction-to-F-3-of-3/

Α programming puzzle: My solution

PALLADIN — Mon, 07 Jun 2010 19:45:00 GMT

Η λύση που έστειλα είναι η Solution2 του darklynx...

	public class Thunk<T>
	{
		private Func<T> func;

		public T Value
		{
			get { return func(); }
		}

		public Thunk(Func<T> computeFunc)
		{
			this.func = () => { func = ((Func<T, Func<T>>)(value => () => value))(computeFunc()); return func(); };
		}
	}

Η τεχνική αυτή μοιάζει λίγο με Jit thunks.

Happy hacking.

Α programming puzzle

PALLADIN — Mon, 07 Jun 2010 01:30:00 GMT

Πριν από λίγες μέρες, ένας φίλος μου έστειλε ένα programming puzzle που του τέθηκε κατά την διάρκεια ενός job interview.

Το σκέφτηκα για λίγο και του έστειλα μια πρόχειρη λύση.

Με το που είδε τον κώδικα που του έστειλα, μου απάντησε ότι αποκλείεται να είχαν κάτι τέτοιο στο μυαλό τους.

Επειδή είμαι περίεργος να δω και άλλες ιδέες για το πρόβλημα, όσοι φίλοι

θέλουν, μπορούν να αφήσουν ένα comment με τις ιδέες τους.

Σε επόμενο blog post, θα δώσω την λύση που του έστειλα.

Το puzzle:

Δώστε μια εναλλακτική υλοποίηση της παρακάτω class χωρίς να χρησιμοποιηθεί

κανενός είδους conditional logic construct (if, switch, ()?).

public class Thunk<T>
{
	private T value;
	private bool flag = false;
	private Func<T> func;

	public T Value
	{
		get
		{
			if(!flag)
			{				
				value = func();
				flag = true;
			}
			return value;	
		}
	}

	public Thunk(Func<T> func)
	{
		this.func = func;
	}
}

Pattern matching in C# (The Scheme way)

PALLADIN — Sat, 10 Apr 2010 19:56:00 GMT

Με αφορμή αυτό το thread, και επειδή ο ξεχασμένος Scheme hacker που κρύβω μέσα μου επαναστάτησε...

σκέφτηκα να συνδυάσω old time classic Scheme hacking και modern C# style API.

public static class PatternMatch
{
    public static Func<Func<TValue, TResult>, Func<TValue, TResult>> With<TValue, TResult>(Func<TValue, bool> condition, Func<TValue, TResult> action)
    {
        return With(value => value, condition, action);
    }
    public static Func<Func<TValue, TResult>, Func<TValue, TResult>> With<TValue, TResult>(this Func<Func<TValue, TResult>, Func<TValue, TResult>> withFunc, Func<TValue, bool> condition, Func<TValue, TResult> action)
    {
        return continuation => withFunc(value => condition(value) ? action(value) : continuation(value));
    }
    public static Func<TValue, TResult> Else<TValue, TResult>(this Func<Func<TValue, TResult>, Func<TValue, TResult>> withFunc, Func<TValue, TResult> elseFunc)
    {
        return withFunc(elseFunc);
    }
}

Example:

var pattern = PatternMatch.With<int, string>(value => value == 1, value => "One ")
                              .With(value => value == 2, value => "Two ")
                              .With(value => value == 3, value => "Three ")
                              .Else(_ => "Else");

Console.WriteLine(pattern(1));

Καλό Σάββατο σε όλους μας.

Robin Milner (13/1/1934 - 20/3/2010)

PALLADIN — Thu, 01 Apr 2010 21:48:00 GMT

Η ML είναι μια από τις γλώσσες που άλλαξαν εντελώς τον τρόπο σκέψης μου.

Ο Robin Milner είναι ένας από εκείνους τους σπάνιους ανθρώπους, που ανέδειξαν το βάθος, την δύναμη και την ομορφιά στο

αντικείμενο που σήμερα ονομάζουμε Computer Science.

Μια προσωπικότητα larger than life.

Reactive Monads

PALLADIN — Sat, 27 Feb 2010 22:06:00 GMT

Το Rx είναι το νέο δημιούργημα του Erik Meijer, και μετά από μήνες ενασχόλησης μαζί του, νομίζω ότι είναι απλά 'a work of genius'.

Αυτό που κάνει είναι να δρα ως compositional glue για events, asynchronous calls και γενικά για push based computations.

Κατεβάστε το από εδώ και αρχίστε να εξερευνείτε τις δυνατότητές του (You will be amazed).

Ως ένα παράδειγμα της μαγείας του, έγραψα ένα κλασσικό mouse move recording and playback.

	    var mouseMoveObservable = Observable.Merge(new Control[] { this, recordButton, stopButton, playButton }
                                                    		.Select(control => Observable.FromEvent<MouseEventArgs>(control, "MouseMove")));

            ReplaySubject<TimeInterval<IEvent<MouseEventArgs>>> replayObservable = null;
            Observable.FromEvent<EventArgs>(recordButton, "Click").ObserveOnWindowsForms().Subscribe(_ =>
            {
                stopButton.Enabled = true; recordButton.Enabled = false;
                replayObservable = mouseMoveObservable.TimeInterval().Record();
                replayObservable.ObserveOnWindowsForms().Subscribe(time => this.Text = String.Format("{0},{1}", time.Value.EventArgs.X, time.Value.EventArgs.Y));
            });

            Observable.FromEvent<EventArgs>(stopButton, "Click").ObserveOnWindowsForms().Subscribe(_ =>
            {
                replayObservable.Dispose();
                stopButton.Enabled = false; playButton.Enabled = true;
            });
            
            Observable.FromEvent<EventArgs>(playButton, "Click").ObserveOnWindowsForms().Subscribe(_ =>
            {
                playButton.Enabled = false;
                var playObservable = replayObservable.ToEnumerable()
                                     .Aggregate(Observable.Return(new Unit()),
                                                (accObservable, timeMouse) => accObservable.Delay(timeMouse.Interval)
                                                                                            .ObserveOnWindowsForms()                                                                                            
                                                                                            .Do(__ => Cursor.Position = ((Control)timeMouse.Value.Sender).PointToScreen(new Point(timeMouse.Value.EventArgs.X, timeMouse.Value.EventArgs.Y))));
                playObservable.Subscribe(value => { }, () => recordButton.Enabled = true);
            });

LiftM'e' up Scotty

PALLADIN — Mon, 08 Feb 2010 07:40:00 GMT

Έχοντας αναπτύξει όλο το απαραίτητο machinery (1, 2), μπορούμε να συνεχίσουμε με την ίδια αφαιρετική διάθεση και να "ανεβάσουμε" στον κόσμο του 'M',
συναρτήσεις με ένα, δυο ή περισσότερα arguments.

// liftM declarations
let liftM<'M, 'A1, 'R when 'M :> MonadDef<'M>> (m : MonadDef<'M>) (f : 'A1 -> 'R) 
                                               (a : IMonad<'A1, 'M>) : IMonad<'R, 'M> = 
                                               m.Map(f, a)

let liftM2<'M, 'A1, 'A2, 'R when 'M :> MonadDef<'M>> (m : MonadDef<'M>) (f : 'A1 -> 'A2 -> 'R) 
                                                     (a : IMonad<'A1, 'M>) (b : IMonad<'A2, 'M>) : IMonad<'R, 'M> =
                                                     m.Apply(liftM m f a, b)

let liftM3<'M, 'A1, 'A2, 'A3, 'R when 'M :> MonadDef<'M>> (m : MonadDef<'M>) (f : 'A1 -> 'A2 -> 'A3 -> 'R) 
                                                          (a : IMonad<'A1, 'M>) (b : IMonad<'A2, 'M>) 
                                                          (c : IMonad<'A3, 'M>) : IMonad<'R, 'M> =
                                                          m.Apply(liftM2 m f a b, c)  

//liftM example
let result = liftM2 listM (+) (listM.OfList [0; 1]) (listM.OfList [0; 2])
printfn "%A" result //[0; 2; 1; 3]

Haskell inspiration
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html

Abstracting over 'M' (generic functions)

PALLADIN — Mon, 18 Jan 2010 04:17:00 GMT

(Haskell ideas => F# (OOP + FP))

Στην Haskell, επειδή έχουμε higher kind polymorphism, μπορούμε να ορίσουμε κάποιες πολύ χρήσιμες και αρκετά γενικές συναρτήσεις για Monads.
Σκέφτηκα να προσπαθήσω να κάνω κάτι αντίστοιχο σε F# (υλοποιώντας ένα Generic List Monad) και να ορίσω τις κλασσικές sequence, mapM, filterM.

Ως παράδειγμα της δύναμης που μας προσφέρει η αφαίρεση, μπορούμε να ορίσουμε την συνάρτηση του powerset ως εξής:
let powerSet xs = listM.FilterM ((fun _ -> listM.OfList [false; true]), listM.OfList xs) // it's magic

Χρησιμοποιώντας subtype polymorphism και μερικά περιορισμένα downcasts, καταφέραμε να φέρουμε λίγο από το άρωμα και την αίγλη της Haskell στον κόσμο της F#.

Happy hacking...

module MonadModule = 
    //Generic Monad Definition
    [<AbstractClass>]
    type MonadDef<'M when 'M :> MonadDef<'M>>() as this = 
         let (>>=) m f = this.Bind(m, f)
         let unit v = this.Return v
         static let listDef = ListDef()

         abstract member Return<'T> : 'T -> IMonad<'T,'M> 
         abstract member Bind<'T, 'S> : IMonad<'T,'M> * ('T -> IMonad<'S,'M>) -> IMonad<'S,'M> 
         abstract member Zero<'T> : unit -> IMonad<'T,'M>
         
         member this.Delay(f) = unit () >>= fun () -> f()
         member this.Combine<'T>(first : IMonad<unit, 'M>, second : IMonad<'T, 'M>) : IMonad<'T, 'M>  = 
            this.Then (first, second)

         member this.Then<'T, 'S>(firstM : IMonad<'T, 'M>, secondM : IMonad<'S, 'M>) : IMonad<'S, 'M> =
            firstM >>= fun _ -> secondM

         member this.Map<'T, 'S>(f : 'T -> 'S, m : IMonad<'T, 'M>) : IMonad<'S, 'M> =
            m >>= fun v -> unit (f v)

         member this.Apply<'T, 'S>(mf : IMonad<'T -> 'S, 'M>, m : IMonad<'T, 'M>) : IMonad<'S, 'M> =
            mf >>= fun f -> m >>= fun v -> unit (f v)   

         member this.Join<'T>(m : IMonad<IMonad<'T, 'M>, 'M>) : IMonad<'T, 'M> =
            m >>= id

         member this.Sequence<'T>(lm : IMonad<IMonad<'T, 'M>, ListDef>) : IMonad<IMonad<'T, ListDef>, 'M> =
            match lm :?> _ with
            | Nil -> unit (Nil :> _)
            | Cons (m, ms) -> m >>= fun v -> this.Sequence ms >>= fun vs -> unit (listDef.ConsM v vs)
        
         member this.MapM<'T, 'S>(f : 'T -> IMonad<'S, 'M>, l : IMonad<'T, ListDef>) : IMonad<IMonad<'S, ListDef>, 'M> =  
            this.Sequence (listDef.Map ((fun v -> f v), l))

         member this.FilterM<'T>(p : 'T -> IMonad<bool, 'M>, l : IMonad<'T, ListDef>) : IMonad<IMonad<'T, ListDef>, 'M> =
            match l :?> _ with
            | Nil -> unit (Nil :> _)
            | Cons (x, xs) -> p x >>= fun b -> this.FilterM (p, xs) >>= fun ys -> if b then unit (listDef.ConsM x ys) else unit ys   

    and IMonad<'T,'M when 'M :> MonadDef<'M>> = interface end 

    // List Monad
    and List<'T> = 
        | Nil
        | Cons of ('T * List<'T>)
        interface IMonad<'T, ListDef>
    and
        ListDef() = 
            inherit MonadDef<ListDef>() with
                member this.OfList<'T>(xs : list<'T>) : IMonad<'T, ListDef> =
                    List.foldBack (fun v acc -> this.ConsM v acc) xs <| this.Zero() 

                member this.ConsM (x : 'T) (acc : IMonad<'T, ListDef>) : IMonad<'T, ListDef> = Cons (x, acc :?> _) :> _
                 
                member this.Foldr<'T, 'S>(f : 'T -> 'S -> 'S, seed : 'S, list : IMonad<'T, ListDef>) : 'S =
                    match list :?> _ with
                    | Nil -> seed
                    | Cons (x, xs) -> f x (this.Foldr (f, seed, xs) )

                member this.Concat<'T>(first : IMonad<'T, ListDef>, second : IMonad<'T, ListDef>) : IMonad<'T, ListDef> =
                    this.Foldr(this.ConsM, second, first)

                override this.Return<'T>(v : 'T) : IMonad<'T, ListDef> = 
                    Cons (v, Nil) :> _ 
          
                override this.Bind<'T,'S>(m : IMonad<'T, ListDef>, f : 'T -> IMonad<'S, ListDef>) : IMonad<'S, ListDef> =  
                    this.Foldr ((fun x acc -> this.Concat (f x, acc)), Nil :> _, m)

                override this.Zero<'T>() : IMonad<'T, ListDef> = 
                    Nil :> _ 
 
    let listM = ListDef()

open MonadModule

// Maybe Monad
module MaybeModule =

    type Maybe<'T> = 
        | Nothing 
        | Just of 'T 
        interface IMonad<'T, MaybeDef> 
    and 
        
        MaybeDef() = 
            inherit MonadDef<MaybeDef>() with
                override this.Return<'T>(v : 'T) : IMonad<'T, MaybeDef> = 
                    Just v :> _ 
      
                override this.Bind<'T,'S>(m : IMonad<'T, MaybeDef>, f : 'T -> IMonad<'S, MaybeDef>) : IMonad<'S, MaybeDef> = 
                    match m :?> _ with 
                    | Nothing -> Nothing :> _ 
                    | Just x  -> f x

                override this.Zero<'T>() : IMonad<'T, MaybeDef> = 
                    Nothing :> _
                
                member this.Just<'T>(value : 'T) : IMonad<'T, MaybeDef> =
                    Just value :> _
                member this.Nothing<'T>() : IMonad<'T, MaybeDef> =
                    Nothing :> _
    
    let maybeM = new MaybeDef()     
 

open MaybeModule


//Examples

let test = listM.OfList [ maybeM.Just 1; maybeM.Just 2 ]
maybeM.Sequence test |> printfn "%A"


let powerSet xs = listM.FilterM ((fun _ -> listM.OfList [false; true]), listM.OfList xs)
powerSet [1..3] |> printfn "%A"

Only for language geeks

PALLADIN — Sun, 27 Dec 2009 22:03:00 GMT

No comment

Abstracting over 'M' (in F#)

PALLADIN — Sun, 20 Dec 2009 23:53:00 GMT

Μετά από αρκετές αποτυχημένες προσπάθειες, στο να συνδυάσω Type constructor polymorphism και LINQ syntax, αποφάσισα
να δοκιμάσω τις ίδιες ιδέες σε F#.

Η F# υλοποίηση είναι ακριβώς ίδια με την αντίστοιχη σε C#, με την μονη διαφορα ότι το Monad generalization δουλεύει με το ειδικό
syntax support που μας παρέχουν τα computation expressions.

[<AbstractClass>]
type MonadDef<'M when 'M :> MonadDef<'M>>() as this = 
     let (>>=) m f = this.Bind(m, f)
     let unit v = this.Return v

     abstract member Return<'T> : 'T -> IMonad<'T,'M> 
     abstract member Bind<'T, 'S> : IMonad<'T,'M> * ('T -> IMonad<'S,'M>) -> IMonad<'S,'M> 
    
     member this.Then<'T, 'S>(firstM : IMonad<'T, 'M>, secondM : IMonad<'S, 'M>) : IMonad<'S, 'M> =
        firstM >>= fun _ -> secondM

     member this.Map<'T, 'S>(f : 'T -> 'S, m : IMonad<'T, 'M>) : IMonad<'S, 'M> =
        m >>= fun v -> unit (f v)

     member this.Apply<'T, 'S>(mf : IMonad<'T -> 'S, 'M>, m : IMonad<'T, 'M>) : IMonad<'S, 'M> =
        mf >>= fun f -> m >>= fun v -> unit (f v)   

     member this.Join<'T>(m : IMonad<IMonad<'T, 'M>, 'M>) : IMonad<'T, 'M> =
        m >>= id

and IMonad<'T,'M when 'M :> MonadDef<'M>> = interface end 

type Maybe<'T> = 
    | Nothing 
    | Just of 'T 
    interface IMonad<'T, MaybeDef> 
and 
    MaybeDef() = 
        inherit MonadDef<MaybeDef>() with
            override this.Return<'T>(v : 'T) : IMonad<'T, MaybeDef> = 
                Just v :> _ 
  
            override this.Bind<'T,'S>(m : IMonad<'T, MaybeDef>, f : 'T -> IMonad<'S, MaybeDef>) : IMonad<'S,MaybeDef> = 
                match m :?> _ with 
                | Nothing -> Nothing :> _ 
                | Just x  -> f x 


let maybe = new MaybeDef() 

let toMaybeString a = 
    maybe { 
        let! v = Just a  
        return v.ToString()
    }

printfn "%A" (toMaybeString 42)

Διομήδης Σπινέλλης

PALLADIN — Fri, 06 Nov 2009 22:11:00 GMT

Πριν πολλά πολλά χρονια... είχα αγοράσει ένα βιβλίο που είχε στο εξώφυλλο ένα ψάρι (the "fish book")!!!
Αυτό που βρήκα περίεργο στο βιβλίο δεν ήταν το ψάρι αλλα αυτός ο κώδικας

/* DDS-BASIC interpreter in "C" annotated by Michael Somos 1997 */
/* INPUT bug fix 07Sep2005 Somos */
/* original by Diomidis Spinellis for 1990 IOCCC
<URL:http://reality.sgi.com/csp/ioccc/1990/dds.c>

#define O(b,f,u,s,c,a)b(){int o=f();switch(*p++){X u:_ o s b();X c:_ o a b();default:p--;_ o;}}
#define t(e,d,_,C)X e:f=fopen(B+d,_);C;fclose(f)
#define U(y,z)while(p=Q(s,y))*p++=z,*p=' '
#define N for(i=0;i<11*R;i++)m[ i ]&&
#define I "%d %s\n",i,m[ i ]
#define X ;break;case
#define _ return
#define R 999
typedef char*A;int*C,E[R],L[R],M[R],P[R],l,i,j;char B[R],F[2];A m[12*R],malloc
(),p,q,x,y,z,s,d,f,fopen();A Q(s,o)A s,o;{for(x=s;*x;x++){for(y=x,z=o;*z&&*y==
*z;y++)z++;if(z>o&&!*z)_ x;}_   0;}main(){m[11*R]="E";while(puts("Ok"),gets(B)
)switch(*B){X'R':C=E;l=1;for(i=0;i<R;P[i++]=0);while(l){while(!(s=m[l]))l++;if
(!Q(s,"\"")){U("<>",'#');U("<=",'$');U(">=",'!');}d=B;while(*F=*s){*s=='"'&&j
++;if(j&1||!Q(" \t",F))*d++=*s;s++;}*d--=j=0;if(B[1]!='=')switch(*B){X'E':l=-1
X'R':B[2]!='M'&&(l=*--C)X'I':B[1]=='N'?gets(p=B),P[*d]=S():(*(q=Q(B,"TH"))=0,p
=B+2,S()&&(p=q+4,l=S()-1))X'P':B[5]=='"'?*d=0,puts(B+6):(p=B+5,printf("%d\n",S
()))X'G':p=B+4,B[2]=='S'&&(*C++=l,p++),l=S()-1 X'F':*(q=Q(B,"TO"))=0;p=B+5;P[i
=B[3]]=S();p=q+2;M[ i ]=S();L[ i ]=l X'N':++P[*d]<=M[*d]&&(l=L[*d]);}else p=B+2,P[
*B]=S();l++;}X'L':N printf(I)X'N':N free(m[ i ]),m[ i ]=0   X'B':_ 0 t('S',5,"w",N
fprintf(f,I))t('O',4,"r",while(fgets(B,R,f))(*Q(B,"\n")=0,G()))X 0:default:G()
;}_ 0;}G(){l=atoi(B);m[l]&&free(m[l]);(p=Q(B," "))?strcpy(m[l]=malloc(strlen(p
)),p+1):(m[l]=0,0);}O(S,J,'=',==,'#',!=)O(J,K,'<',<,'>',>)O(K,V,'$',<=,'!',>=)
O(V,W,'+',+,'-',-)O(W,Y,'*',*,'/',/)Y(){int o;_*p=='-'?p++,-Y():*p>='0'&&*p<=
'9'?strtol(p,&p,0):*p=='('?p++,o=S(),p++,o:P[*p++];}

Τι θέλει να πει ο ποιητής και ποιος είναι αυτός ο Διομήδης Σπινέλλης,,,μετά από κάποια χρονια έμαθα!!!
Πολλά συγχαρητήρια και από εμενα...
Πόσες χώρες έχουν έναν hacker σε τέτοια θέση!!!

Abstracting over 'M'

PALLADIN — Mon, 26 Oct 2009 00:34:00 GMT

Τον τελευταίο καιρό ψάχνω κάποιο φορμαλισμό (σε C#) ώστε να μπορέσω να έχω έναν generic-reusable ορισμό ενός Monad.
Αυτό που λείπει από τα .Net generics είναι η δυνατότητα να έχω abstraction σε επίπεδο Type Constructor.

Σαν παράδειγμα της συγκεκριμένης αφαίρεσης, παρουσιάζω τον generic ορισμό ενός Monad μέσα από δυο αγαπημένες μου γλώσσες.

Haskell
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a


Scala
class Monad[M[_]] {
	def unit[T](a: T): M[T]
	def bind[T, K](m: M[T], f: T => M[K]): M[K]
}

Μετά από αρκετό πειραματισμό και μελέτη, κατέληξα στον παρακάτω κώδικα.

	abstract class Monad<T, M> where M : MonadDef<M> { }
	abstract class MonadDef<M> where M : MonadDef<M>
	{
		public abstract Monad<T, M> Unit<T>(T value);
		public abstract Monad<S, M> Bind<T, S>(Monad<T, M> monad, Func<T, Monad<S, M>> func);

		public Monad<S, M> Then<T, S>(Monad<T, M> first, Monad<S, M> second)
		{
			return Bind(first, _ => second);
		}

		public Monad<S, M> Map<T, S>(Monad<T, M> monad, Func<T, S> f)
		{
			return Bind(monad, value => Unit(f(value)));
		}

		public Monad<T, M> Join<T>(Monad<Monad<T, M>, M> monad)
		{
			return Bind(monad, value => value);
		}
	}
	// Maybe Monad implementation 
	abstract class Maybe<T> : Monad<T, MaybeDef>
	{
	}
	sealed class Just<T> : Maybe<T>
	{
		public T Value { private set; get; }
		public Just(T value) { Value = value; }
	}
	sealed class Nothing<T> : Maybe<T> { }

	static class MaybeMonadExtensions
	{
		public static Maybe<T> ToMaybe<T>(this Monad<T, MaybeDef> monad)
		{
			return (Maybe<T>)monad;
		}
	}

	sealed class MaybeDef : MonadDef<MaybeDef>
	{

		public override Monad<T, MaybeDef> Unit<T>(T value)
		{
			return new Just<T>(value);
		}

		public override Monad<S, MaybeDef> Bind<T, S>(Monad<T, MaybeDef> monad, Func<T, Monad<S, MaybeDef>> f)
		{
			Just<T> just = monad as Just<T>;
			if (just != null)
				return f(just.Value);
			else
				return new Nothing<S>();
		}
	}
 
         static void Main(string[] args)
	{
            var def = new MaybeDef();
            Maybe<string> result = def.Bind(def.Unit(42), value => def.Unit(value.ToString())).ToMaybe();
         }

RegEx engine in F#

PALLADIN — Sun, 27 Sep 2009 21:54:00 GMT

Ένα από τα πολύ δυνατά χαρακτηριστικά μιας functional γλώσσας, είναι η δυνατότητα να δημιουργούμε internal DSLs κάνοντας compose combinators.

Ένα τέτοιο παράδειγμα, είναι μια regex engine που έγραψα σε F#.

Κάποιες βασικές ιδέες της υλοποίησης:
- lazy computations for backtracking
- combinators for regex composition
- parametric polymorphism: Generic "named capture variables" and input sequences
- Unions + Active Patterns: pattern matching and value extraction

Ακολουθεί ένα sample

#r "FSharp.PowerPack.dll"
#load "RegEx.fs"

open System
open RegEx

// example from http://www.martinfowler.com/bliki/ComposedRegex.html

type extractTags = NumberOfPoint of int | NumberOfNights of int | HotelName of string
let numberOfPoints = toInt >> NumberOfPoint
let numberOfNights = toInt >> NumberOfNights
let hotelName  = toString >> HotelName

let scoreKeyword() = string "score" => !+ space()
let numberOfPoints = !+ digit() |> group numberOfPoints
let forKeyword() = space() => string "for" => space()
let numberOfNights = !+ digit() |> group numberOfNights
let nightsAtKeyword() = spaces() => string "nights" => spaces() => string "at" => spaces()
let hotelName() = !+ any() |> group hotelName

let pattern = scoreKeyword() => numberOfPoints => forKeyword() => numberOfNights => nightsAtKeyword() => hotelName() => endOfLine()

let text = List.reduce (fun acc value -> acc + "\r\n " + value)
              [ "score 400 for 2 nights at Minas Tirith Airport"; 
                "score 500 for 6 nights at Athens Airport";
                "score 200 for 3 nights at London Airport" ] + "\r\n"

let result = patternMatch pattern text

// pattern match
match result with
| Success ( (NumberOfPoint(points) :: NumberOfNights(nights) :: HotelName(name) :: _) :: _ ) -> printfn "Points: %d, Nights %d, Hotel name: %s" points nights name
| Failure -> ()

                
let replacePattern = function
| [NumberOfPoint(points); NumberOfNights(nights); HotelName(name)] -> sprintf "score %d for %d nights at %s" (points * 2) (nights * 3) (name + " ok")
| _ -> failwith "Expected extraction pattern: score {NumberOfPoint} for {NumberOfNights} nights at {HotelName}"

let replacedResult = patternReplace pattern text replacePattern |> Array.of_seq |> (fun (chars : array<char>) -> new String(chars))

letrec

PALLADIN — Mon, 14 Sep 2009 05:44:00 GMT

Ο Bart de smet συνεχίζει την πολύ καλή σειρά από posts, και αυτή την φορα μας παρουσιάζει ένα cache Enumerable, μαζί με έναν "let" binder.
Φυσικά λείπει το αδελφάκι "letrec", όπου έμεινε ως άσκηση για τον αναγνώστη.
(η αφορμή που έψαχνα για να ξυπνήσει Ο old schemer μέσα μου)

		delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
		static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
		{
			Recursive<A, R> rec = r => a => f(r(r))(a);
			return rec(rec);
		}
		public static IEnumerable<U> Let<T, U>(this IEnumerable<T> source, Func<IEnumerable<T>, IEnumerable<U>> function)
		{
			using (var mem = new MemoizeEnumerable<T>(source))
			{
				foreach (var item in function(mem))
					yield return item;
			}
		}
		public static IEnumerable<U> LetRec<T, U>(this IEnumerable<T> source, Func<Func<IEnumerable<T>, IEnumerable<U>>, Func<IEnumerable<T>, IEnumerable<U>>> function)
		{
			Func<Func<IEnumerable<T>, IEnumerable<U>>, Func<IEnumerable<T>, IEnumerable<U>>> letWrap =
				f => x => Let(x, function(f));

			return Y(letWrap)(source);
		}