F# – Duck Typing and Structural Typing

As you may have noticed on this blog lately that I’ve been focusing on Asynchronous Workflows.  In those adventures, I’ve been taking well known APIs such as Twitter, Bing, among others and seeing what I can do with them.  In this instance, when using LINQ to XML, I’ve run into a slight syntax problem.

The Problem with LINQ to XML

The syntax problem I had revolves around the retrieval of an XElement from the given XContainer.  The signature of this is as follows:

public abstract class XContainer : XNode {
    public XElement Element(XName name);
}

But, what you may not realize is that there is an implicit operator which allows us to implicitly convert a string to an XName with little effort such as this:

public sealed class XName : IEquatable<XName>, ISerializable {
...
    public static implicit operator XName(
        string expandedName);
}

This allows us to use a string instead of an XName when specifying which element name we want, including namespace if desired, rather easily. 

var document = XDocument.Parse(xml);
var statuses = document.Root.Descendants()
    .Select(node => node.Element("text").Value);

Unfortunately for us, this behavior does not work in the current F# release. 

> document.Root.Descendants() 
-   |> Seq.map(fun node -> node.Element("node").Value);;

stdin(5,65): error FS0001: This expression has type
        string
but is here used with type
        XName

It does not recognize this implicit operator.  What options do we have around this?  One simple answer might be just a simple function that does the conversion for us, such as this:

> let ( !! ) : string -> XName = XName.op_Implicit;;
val ( !! ) : string -> XName

> let xFoo = !!"foo";;
val xFoo : XName = foo

What we’re now able to do is convert at will using the !! operator, or what I call the “Convert Dammit” operator.  But, there is another solution worth exploring that is a bit more generic through the use of duck typing.

Duck Typing to the Rescue?!?

For those unfamiliar with the term duck typing, it is a style of dynamic typing in which the object’s current set of methods, properties, etc, determines its validity instead of its inheritance chain.  In F#, we have the ability to use this mechanism to use this to our advantage to create generic functions.  For example, let’s take the implicit operator example from above and use duck typing instead of the direct call to the XName class.

// Longhand
let inline implicit< ^a,^b when ^a : (static member op_Implicit : ^b -> ^a)> arg =
  ( ^a : (static member op_Implicit : ^b -> ^a) arg)
  
// Shorthand - let the compiler do the work
let inline implicit arg =
  ( ^a : (static member op_Implicit : ^b -> ^a) arg)

The two above statements are syntactically the same, although in the latter version, I don’t have to clutter up my declarations as much and instead let the compiler type inference magic do its work.  From here on out, I’ll use the shorthand unless the longhand doesn’t quite work out.  What you’ll notice is that I have a requirement for my ^a generic to have a restriction that it must have the implicit operator declared.  Then we can execute said operation by passing in our argument.  I can rewrite the convert dammit operator then to look something like this:

open System.Xml.Linq
let (!!) : string -> XName = implicit

let xFoo = !!"foo" // Our new XName

Now you can see here that I didn’t explicitly have to call anything on XName as I let the implicit operator do the work for me.  Best of all here is that it’s now statically typed to that any call to implicit must have that operator defined on it, else it will not compile.

But, let’s not stop there, you can continue on all sorts of tangents.  What about functions which have more than one argument?  Let’s take the addition operator.  Could we use duck typing in our favor for this?  Although it’s not recommended, the answer is yes. 

> let inline add arg1 arg2 = 
-   ( ^a : (static member op_Addition : ^a * ^b -> ^a) (arg1, arg2))
val inline add :
   ^a ->  ^b ->  ^a when  ^a : (static member ( + ) :  ^a *  ^b ->  ^a)

> open System;;
> let addedTime = add DateTime.Now (TimeSpan.FromSeconds 5000.);;
val addedTime : DateTime = 6/11/2009 1:00:32 PM

The reason why it’s not recommended is that a lot of primitive types are implicitly augmented with this operator such as int, float, etc, so this would not work for those plus not work on string as well since dynamic invocation is not allowed on this particular instance. 

This is useful though in other scenarios.  Take for example extracting a Name property from a given class.  Once again, using the methodologies from above, it’s rather simple:

let inline getName arg =
  ( ^a : (member Name : string) arg)
  
open System
open System.IO
let fName = getName (new FileInfo("fsi.exe"))
let dName = getName (new DirectoryInfo(Environment.CurrentDirectory))

What about multiple restrictions?  That’s not too difficult either.  Let’s do the canonical Duck example with a little twist.  First, we will define the overall function which will extract the Flying and Walking state of a given class.

let inline flyAndWalk arg =
  let flying = ( ^a : (member Fly : unit -> string) arg)
  let walking = ( ^a : (member Walk : unit -> string) arg)
  (flying, walking)

And now we can define our classes which have the methods which have our interest such as the Fly and Walk methods.  We execute each of these, obtain the result and finally return the results of each as a tuple.  Now, let’s define two classes below of a Duck and an Eagle.

type Duck() =
  member this.Swim() = "paddling"
  member this.Fly() = "flapping"
  member this.Walk() = "waddling"
 
type Eagle() =
  member this.Fly() = "soaring"
  member this.Walk() = "creeping"
 
let (eFly, eWalk) = flyAndWalk (new Eagle())
let (dFly, dWalk) = flyAndWalk (new Duck())

Our final result will be rather predictable as you might imagine.  Just as well if we put a Penguin class which contains no fly, well, then this class won’t compile as shown below in F# interactive:

> type Penguin() =
-   member this.Walk() = "waddle"
-   member this.Swim() = "swimming";;

type Penguin =
  class
    new : unit -> Penguin
    member Swim : unit -> string
    member Walk : unit -> string
  end

> let (pFly, pWalk) = flyAndWalk(new Penguin());;

  let (pFly, pWalk) = flyAndWalk(new Penguin());;
  -------------------------------^^^^^^^^^^^^^

stdin(84,32): error FS0001: The type 'Penguin' does not support any operators na
med 'Fly'

As you can see, it’s a rather powerful concept, when used in moderation, can help you solve some interesting problems such as implicit operators as well as other scenarios.

Structural Typing

There is a concept that is prevalent in languages such as OCaml, ML, and Scala for Structural Typing as opposed to Duck Typing.  This is a concept in which compatibility and equivalence is based upon the type’s structure and not the explicit declarations as I’ve had above.  Equivalence is then measured by the structural sameness between the two even though they may be nothing more than anonymous objects.

In F#, we can accomplish this in a sense through the use of the record type quite easily.  For example, we can define a class that has two properties and then check for sameness between them.

> type Foo = { X : int; Y : int};;

type Foo =
  {X: int;
   Y: int;}

> {X=32;Y=45} = {X=32;Y=45};;
val it : bool = true

Normally, given that these are reference types and not standard structures, they shouldn’t ordinarily equate one to another automatically, but F# through the use of structural typing, does allow for this.  The same also applies for Discriminated Unions as well such as the following:

> type DU = A of string | B of int;;

type DU =
  | A of string
  | B of int

> B 42 = B 42;;
val it : bool = true

Once again, since they are reference types, they shouldn’t equal each other, but with F#, they do, through the use of structural typing. 

Conclusion

Through the use of structural typing and duck typing, we realize how flexible the F# language really is.  This gives us the ability to be creative in how we solve our problems generically in specialized cases such as our LINQ to XML example from above.  Now that F# is a full citizen in the .NET space with Visual Studio 2010, it’s even more exciting about what we can do with the language.

This entry was posted in F#, Functional Programming, OOP. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • http://richiban.wordpress.com Richard Gibson

    First of all I think that the content of your post is mostly good, but I think you’ve misunderstood a few things here.

    1. Duck typing has nothing to do with dynamic typing; they’re two completely separate concerns.
    2. Your last paragraph is titled “Structural Typing” but what you actually describe is “Structural Equality” which is something very different. Structural typing is essentially the same thing as duck typing but applied specifically to compiled languages (Google Go does this, where interfaces are not explicitly implemented).

    Other than that keep it up!