Comments

Very nice solution! How does it deal with empty sequences? I assume Take and Skip don't throw exceptions on empty sequences?

 

I think my only suggestion would be to check if s is empty first, then you can rewrite:

 

public static IEnumerable<T> Qsort1<T>(this IEnumerable<T> s) where T : IComparable<T>
{

    return ! s.Any() ? Enumerable.Empty<T>() :
        from x in s.Take(1)
        let xs = s.Skip(1)
        let a = xs.Where(y => y.CompareTo(x) <= 0).Qsort1()
        let b = xs.Where(y => y.CompareTo(x) > 0).Qsort1()
        select a.Concat(s.Take(1)).Concat(b);
}

 

But I don't know if that is allowed syntax.

I love it! Glad to see this happening. I can't wait for the hard stuff.

 

One comment - though you are focusing on Haskell, please keep it tied to C# (e.g., "here's how to do it in C#") and keep it practical. By comign back to C#, unfamiliar concepts look familiar. By keeping it practical, we'll see how this stuff can really be used. Haskell - not just for Fibonacci anymore! OK that's a bit facetious.

 

As for the homework, here is my solution. I basically transcribed the Haskell version shown. I am sure it can be prettier:

 

public static IEnumerable<A> QuickSort<A>(IEnumerable<A> vals)
            where A : IComparable<A>
        {
            if (vals.Skip(1).IsEmpty())
                return vals;
            else
            {
                A pivot = vals.First();
                var rest = vals.Skip(1);
                var left = from x in rest
                           where x.CompareTo(pivot) <= 0
                           select x;

                var right = from x in rest
                            where x.CompareTo(pivot) > 0
                            select x;

                return QuickSort(left).Concat(vals.Take(1)).Concat(right);
            }
        }

 

Note : IsEmpty is an extension method which tests if a sequence is empty. I can't believ that is not already defiend in the framework so I am sure i missed it.

 

I particularly like the end part, where I concatenate the single pivot value into the sequence:

 

  return QuickSort(left).Concat(vals.Take(1)).Concat(right);

 

Since the list is not empty, I know I can take the first value and stick in the right place. My base case also takes advantage here:

 

           if (vals.Skip(1).IsEmpty())
                return vals;
            else

                 ...

 

If the sequence given only has one element, I just return it unchanged and it automatically goes in the right spot. Thank you recursion!

 

Full source code & VS2008 project available on github.

 

Justin

You guys never got to Until (mentioned in part 1). Any follow up details?

 

I also wish you'd talk more about Let. How is that implemented? Does it give you lazy computation? E.g. Haskell lets your write:

 

  zero = let x = x in 0

 

And you won't get an infinite loop. Does Let allow somethign similar?

 

Good stuff!

Pretty cool work. I think your implementation points out a few issues that this approach has to deal with.

 

1) SpotAgent allows many subscribers; RiskAgent only one -- That says the Subscribe method isn't giving enough information (and the IObservable interface isn't rich enough). I wonder how you could indicate that a given Observable allows many observers vs. one?

 

2) One problem that Erik points out with IEnumerable is the "subscriber" which calls GetNext() has no control over how long the "publisher" take to return the next value. I think IObservable reverses this problem. That is, the "publisher" (IObservable object) has no control over how long given "subscriber's" (IObserver) OnNext method will take to complete. You can see this issue in the Tick() methods for SpotAgent and RiskAgent.

 

Does the composobility of IObservable/IObserve help solve this problem?

 

Looking at your code definitely exposes some issues that I'm sure Erik's team has faced when developing their library.

Great video! Really fascinating. I can't wait to see the code - just push it to me

A question: The scope of the  IDisposable object returned by Subscribe() was unclear to me. Erik implies you can put it in a using statement, like a normal IDisposable. But the lexical scope of the IDisposable returned seems much different than the lifetime ("runtime scope"?) of the IObserver you pass in. For example, the using statemetn with IDisposable for files is pretty obvious:

  using(fs = new Stream("somefile.txt"))   
  {     
    // ... do work on fs ...   
  } // fs is closed and disposed. 

But in the IObserver case, I don't think the using statement's scope is appropriate for indicating you don't care about events anymore. Using the autocomplete example above:

using(q.Subscribe(suggestions => ... ))
{
  // ???
} 

What happens in the body of the using statement? All the work seems to occur in the lambda passed to Subscribe. If I understood correctly, as soon as we leave the scope of the using statement, my lambda stops receiving events. Hmm, I bet the object implementing IDisposable has the secret sauce for the reactive framework. Maybe it has a method for testing for conditions and will "yield" until the condition is met? For example if I had another observer which looked for ENTER or TAB on the textbox and indicated that a selection was made, maybe it would let me write this code:

class KeyObserver :  IObserver<...>
 {
    publi c bool SelectionMade()
 }

KeyObserver key = ...;

using(cntrl = q.Subscribe(suggestions => ... ))
{
   if(! key.SelectionMade())
     sleep;
} 
// selection has been made and we stop listening to suggest events

Hopefully that makes some sense. It looks like the beginnings of a way to do reasonable event based programming. Apologies for answering my own question but glad to hear if I'm on track ...

Two other notes:

• Check out the AsyncEnumerator library from Jeffrey Richter. He leveraged enumerators and iterators to do something similar, but I think his solution still has an "inversion of control" problem where you need to write the code to drive the enumerator. A recent article can be found at http://msdn.microsoft.com/en-us/magazine/cc721613.aspx
• Erik mentioned a paper by Phillip Wadler called "The essence of monads" or similar. I think he meant "The essence of functional programming" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.9516).

 

Great stuff, get me this code!

Justin

Codebook sounds so cool! It would be even better if it could index legacy code in foreign source control providers. For example, my employer has an application which uses  Pick Basic, PHP, C#, C, SQL, and more. Indexing and tracking all of that would be very cool.

The discussion at the end about the irrelevance of intermediate languages was interesting. I've been dabbling in this area recently and intermediate languages seem to help make compiler/interpreter implementation simpler, but they can lack details you'd like to have in order to produce faster/smaller/safer code.

On the flip side, at one point Lars said why not compile F# to C#, instead of MSIL. I say you are then hampered by the semantics of C#. Quite a few functional languages compile to C and they all suffer from the tailcall problem and have to generate really unnatural C code (the well-known "trampoline" solution). One advantage of an IL is it can expose features that higher-level languages do not. C# has no concept of a "tailcall", but IL allows it.

Another argument is that an IL is really an "API ", just a weird one. Programs on either side of the API can change, but as long as the API and its behavior is stable, they can change independently. The same would be true if you generated C# but I would argue that is the kind of API I don't want to code to.

Anyways, great discussion as always!

p.s. Erik how can you say only Haskell compilers are written in pure Haskell? For shame!

Charles -

Thanks for following up! Looking forward to it ...

Charles - have you seen Code Canvas frmo Kael Rowan at MSR? It looks SOOO cool and the only info out there is an old video on his blog. Will you consider talking to him? I want to know more! Check out the video at http://blogs.msdn.com/kaelr/archive/2009/03/26/code-canvas.aspx.

Sorry to hijack here, but I'm not sure how else to get in touch with Charles.

Can't wait to watch this E2E - thanks again to you and Erik. When are we going to see Erik's lectures???

I ran out and got a copy of Intro to Functional Programming after watching this. I can't wait to see Erik's lectures. Always interesting!