Back to Questions
11.5k
views7
comments
Some notes on Structural Comparison and Hashing
f#functionalcollectionsclassescomplexity

DeeJay has just written an article showing how to implement a binomial heap using F#, adopting a purely functional style. One of his questions concerns structural comparison in F#. In this article I'll give a brief description of what structural comparison is and how you can define the meaning of structural comparison on your new type definitions.

Firstly, every time you're using operators such as <, >, <=, >=, =, <>, 'compare', 'min' and 'max' in F# code you may be invoking structural comparison. You may also be using structural comparison and structural hashing when you use the default configurations of F# data structures such as Set, Map, HashSet and HashTable (see also Hashtbl module) or when you instantiate .NET data structures using the values produced by Microsoft.FSharp.Collections.HashIdentity.Structural (new in F# 1.1.11.4).

On ordinary simple types like integers and strings structural comparison does exactly what you expect. It also works just as you'd expect for .NET types that implement the IComparable interface, e.g. System.DateTime values. However, they great thng is that you can also use these operators on structured types. For example, you can use them on F# tuple values, where a lexicographic left-to-right comparison is used:

1
2
3
4
5
6

> ("abc","def") < ("abc","xyz");;
val it : bool = true

> compare (10,30) (10,20);;
val it : int = 1

As you can see, the purpose of structural comparison is to compositionally extend the orderings on primitive nodes to give a total ordering to concrete tree or DAG structured data. For example, you can also use structural comparison with list and array values:

1
2
3
4
5
6
7

> compare [10;30] [10;20];;
val it : int = 1
> compare [| 10;30 |] [| 10;20 |];;
val it : int = 1
> compare [| 10;20 |] [| 10;30 |];;
val it : int = -1

The F# informal language specification has a section on structural comparison and hashing. In F# 1.1.10 the definition of structural comparison on some other types such as arrays is built into the F# compiler. In the soon-to-be-releaed F# 1.1.11.x these will be more transparent as this code will be implemented in F# code in the F# library fslib.dll itself. It's important to note tht structural comparison is not implemented using reflection - instead code is auto-generated for each type definition that implements comparison efficiently and where possible uses "fast path" comparison techniques, e.g. the generated code will use primitive IL/native instructions for integer comparisons. This means that in practice structural comparison is typically very very fast when used with appropriately sized keys.

By default, every new F# type definition is given an implementation of structural comparison. DeeJay's particular question is whether the semantics of structural comparison can be modified for new type definitions. The answer is yes! It's done simply by implementing the interface Systemm.IComparable. Here's an example, taken from the F# library. Firstly, the type definition includes a promise that the type will implement the the two relevant interfaces:

1
2
3
4
5
6
7

type BigInt 
  = { sign : int; v : BigNatOps.n }
  with
       interface System.IComparable
       interface IStructuralHash
  end

If you like you can define the implementations of these interfaces immediately at the point of the type definition. However you can also use a module of F# code that implements the functionality using a value-oriented style, which can be very useful for controlling the complexity of an implementation. Here's a fragment of the BigInt implementation, defining lessThan in terms of operations defined for BigNat:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 

module BigIntOps = begin 
  module N = BigNatOps   

   ... 
  let lessThan x y =
    match x.sign,y.sign with
    |  1, 1 -> N.lessThan x.v y.v                      //  1.xv <=  1.yv iff xv <= yv 
    | -1,-1 -> N.lessThan y.v x.v                      // -1.xv <= -1.yv iff yv <= xv 
    |  1, -1 -> false
    | -1, 1 -> not (N.isZero x.v) || not (N.isZero y.v)
    | _ -> invalid_arg "z signs should be +/- 1"
...
  let compare n nn = if lessThan n nn then -1 else if equal n nn then 0 else 1

end

You then later in the file augment the type definition with the implementations of these interfaces:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

type BigInt 
  with 
    static member ( + )(n1,n2) = RawBigIntOps.add n1 n2
    static member ( * )(n1,n2) = RawBigIntOps.mul n1 n2
    static member ( - )(n1,n2) = RawBigIntOps.sub n1 n2 
    static member ( / )(n1,n2) = RawBigIntOps.div n1 n2
    static member ( ~- )(n1)  = RawBigIntOps.neg n1
    static member ( ~+ )(n1:BigInt) = n1
    override x.ToString() = RawBigIntOps.to_string x
    override x.GetHashCode() = RawBigIntOps.hash(x)
    interface System.IComparable with 
       member x.CompareTo(y:obj) = RawBigIntOps.compare x (y :?> BigInt)
    end 
    interface IStructuralHash with 
       member x.GetStructuralHashCode(_) = RawBigIntOps.hash(x) 
    end 

  end

Some notes:

  • The above sample also shows the syntax to override the overloaded operators +,- etc. and the method ToString and GetHashCode.
  • It also shows how to implement the interface IStructuralHash. Structural hashing is very simlar to structural comparison, but with the additional twist that hashing can be depth-limited, because you typically want to avoid hashing all of a large term (this is why we don't simply override GetHashCode). I'll save the details for another blog entry. The notes in the language specification also give more details on this.
  • A cast is currently necessary when implementing IComparable. In a future version of F# you will only need to implement IComparable<T>.

Some general additional notes on structural comparison and hashing:

  • Performance: Structural comparison and hashing are incredibly useful and are also efficient over small key terms. However, there are naturally performance issues when using structural comparison over large structured terms. In high-performance situations you should be careful to use small keys, and where necessary define your own comparison and hashing functions.
  • Non-tree structured data: You should not use structural comparison and hashing on recursive data structures (including ones using pointers) or data that you mutate.
  • NaN: when used immediately on floating point numbers, the comparison and equality operators "<" etc. implement IEEE NaN semantics, i.e. returning "false" if either value is a NaN (this is correctly implemented as of version 1.1.11.x)

Please feel free to ask for clarifications on any points regarding the specification of structural comparison and hashing

Cheers!

Don

Addendum:

DeeJay asks some great questions:

So because of this... is there any reason at all to be able to pass in custom comparators? If there is any gain, is it worth the hassle of more complex implementation over just declaring your comparator when you declare your type?

...Comparing to Haskell with it's type classes... .

Comparing to SML and OCaml with it's functors...

With F# I'm very interested in both the theoretical and pragmatic concerns, and ultimately there are some tradeoffs here.

My advice for accessible, reusable data structures is "sensible defaults, ultimate control". That is, provide default constructors based on structural versions of compare/hash, and then provide additional constructors that permit explicit configuration of compare/hash. This is the style followed by the Microsoft.FSharp.Collections.HashTable implementation and the other F# collections (sets, maps, hash sets) will go the same way over time. It is also roughly the style followed by the .NET collections, with the exception that the default comparison used by the .NET collections is not exactly F# structural comparison, but an approximation of it - e.g. it won't structurally compare arrays, though will structurally compare tuples and all other F# data types.

Re functors and type classes:

  • I know this gives slightly weaker guarantees than using functors. This is because instances of the data structure that use different compare/hash are not different types. However it does give the reusability and flexibility of functors, while making the data structures easier for beginners to use.

  • I know this makes the data structures slightly longer to write than when using type classes (since you have to pass the compare/hash explicitly). However, while I love type classes and am considering them for F#, they can lead to problems with flexibility - if you want to use a different comparison function you're a bit stuck.

So I advocate the tasteful application of the "sensible defaults, ultimate control" approach to give a good balance: a simple way to get going with using the data structure (beginners can just start using the data structure on simple types without problems), and it gives experienced users the flexibility they need (e.g. case-invariant comparison on strings is often required).

.

Firma Dobrucki to przewozy autokarowe w graniach kraju i międzynarodowe do większości krajów w Europie. Przygotowaliśmy ofertę, która jest dostosowana do potrzeb wszystkich klientów, którzy cenią sobie wygodę i bezpieczeństwo. W taborze znajdują się markowe autobusy dostosowane do wyjazdów międzynarodowych oraz wygodne busy dla mniejszych grup. Nasza firma to nie tylko wynajem autokarów i wynajem busów. Specjalizujemy się dodatkowo w kompleksowej naprawie powypadkowych samochodów i autobusów. Dzięki długoletniemu doświadczeniu jesteśmy w stanie zreperować każdy zepsuty pojazd i przywrócić mu wygląd sprzed wypadku.

przewozy autokarowe

przewozy autokarowe

By on 8/15/2011 5:24 AM ()

Hello. And Bye.HeyYYYYYYY

103

By on 3/17/2011 9:01 PM ()

Sometimes I like a little something extra out of my online gaming. There has been a lot of buzz lately about websites where we can put some cash down on our online gaming for xbox or PS3. I have used several of these sites and thought I would share my experiences with them.

Virgin Gaming: [link:virgingaming.com]

Pros: Big cash prizes, automatic reporting

Cons: Noobish user base, inconsistent website makes it hard to find a match sometimes

Virgin is the biggest player with the most marketing dollars behind their site, but their inconsistent website is buggy and confusing. They have automatic reporting on all matches and a wide selection of games, but there seems to be many low rent players who use the service and its hard to find a good challenge.

Rivalspot: [link:www.rivalspot.com]

Pros: Weekly free tournaments with nice prizes, automatic reporting, great website

Cons: Still not a lot of users, less games

Rivalspot is a newcomer with a lot of potential, but they are still a bit young. They have weekly tournaments posted on their Facebook page where you can play for free and have a reasonable chance at winning a cash prize at the end. I like their blog, where they post a lot of great sports content, and there are a lot of great players who use the site - it is just still starting out so there aren't as many users online at any given time.

Gamersaloon: [link:www.gamersaloon.com]

Pros: Easy to find a game, good userbase, good game selection

Cons: No automatic reporting

Gamersaloon could be a strong player but to me the lack of automated reporting is a deal breaker. I just can't bring myself to trust some guy in some unknown part of the country being honest about the fact that I just pwned him.

Overall I always try Rivalspot first - they have the most potential IMHO, and when I can't find a match there I jump on to Virgin.

I know there are other similar sites out there, so I was hoping to make this into a thread where we can post about our experiences and maybe hook up for some cash gaming.

By on 3/17/2011 10:31 AM ()

[link:kamagrapharma.blogspot.com]

Treten Sie mit Ihrem Doktor oder Apotheker für mehr Details in Verbindung.Schützen vor Feuchte und Tageslicht!Lagerung Lagern bei einer Zimmertemperatur zwischen 68-77 G (20 und 25 Grad Celsius).Vorsichtsmaßnahmen bevor Sie anfangen, Sildenafil zu nehmen, informieren Sie Ihren Doktor oder Apotheker, wenn Sie dazu allergisch sind; oder wenn Sie irgendwelche anderen Allergien haben.Alle Anweisungen für einen bestimmten Patienten sollen mit Ihrem Gesundheitspflegeberater oder Doktor, der für den Fall verantwortlich ist, übereingestimmt werden.Viele Menschen benutzen diese Medizin ohne ernste Nebenwirkungen.

Sildenafil beeinflusst die Reaktion zur sexuellen Anregung.Die ernste allergische Reaktion auf diese Medizin kann sehr selten auftreten und in diesem Fall brauchen Sie sofortige medizinische Hilfe.Verbrauch-Details Kamagra Mundgelee wird mündlich 15 bis 20 Minuten vor jeder möglicher sexuellen Aktivität verbraucht.Kamagra Mundgelee wird direkt in den Blutstrom aufgesogen und folglich erfordert es unterere Dosen, ähnliche Ergebnisse als das jeder möglicher anderen Medizin zu erzielen.Wir sind nicht für direkte, indirekte, spezielle oder andere indirekte Beschädigung irgendwelcher Art, sowie auch für Folgen Ihrer möglichen Selbstbehandlung nicht verantwortlich.Eine fettreiche Mahlzeit kann die Zeit des Effektes dieser Medizin verzögern.Wir müssen jede Haftung für Schäden ablehnen, die aus einer missbräuchlichen Nutzung von den Informationen auf dieser Seite entstehen kann.Dosierung und Anwendungsgebiet: Viagra Oral Jelly muss bei der Notwendigkeit genommen werden, ungefähr 1 Stunde vor dem Geschlechtsverkehr.Sildenafil kann für andere Zwecke auch verwendet werden, die nicht oben verzeichnet wurden.Bewahren Sie die Medizin in dem Badezimmer nicht.Haftung Wir stellen Ihnen nur die allgemeine Information über die Medizin zur Verfügung vor, die nicht alle Anweisungen, möglichen Wechselwirkungen oder Vorsichtmaßnahmen umfasst.Kamagra Mundgelee enthält Sildenafil Zitrat und wird in der Behandlung der aufrichtbaren Funktionsstörung in den Männern verwendet.Weg von Kindern und Haustieren halten.Verpasste Dosis Sie müssen diese Medizin nur bei der Notwendigkeit einnehmen, und brauchen keinen Plan für die Einnahme.Außer Reichweite von Kindern und Haustiere!Mögliche Nebenwirkung die möglichst oft auftretenden Nebenwirkungen sind Kopfschmerzen, Flushing , Übelkeit oder Magenverstimmung, verstopfte oder laufende Nase , Gedankenlosigkeit, Diarrhöe.Lagerung Kamagra Munddes gelee-15 und 30 Grad c-(59 und 86 Grade Fahrenheit) bei Zimmertemperatur speichern.Produktbeschreibung Allgemeine Anwendung Sildenafil ist der Hauptbestandteil von Viagra Oral Jelly www.Wechselwirkung diese Medizin soll nicht mit den Nitraten und entspannenden Arzneimitteln verwendet werden, die ?Gealterte Leute können für die Nebenwirkungen der Medizin empfindlicher sein.Es sollte einen Tag nicht mehrmals genommen werden.Diese Aufzählung kann unvollständig sein.Versuchen Sie, Grapefruit nicht zu essen oder Grapefruitsaft nicht zu trinken, während Sie mit Sildenafil behandelt werden.Diese Entspannung erlaubt erhöhten Blutfluss in die bestimmten Bereiche von Penis, und das führt zur Aufrichtung.Die Information, die auf dieser Seite ausgestellt ist kann nicht für die Selbstbehandlung oder für die Eigendiagnostik verwendet werden.Treten Sie mit Ihrem Doktor oder mit dem Apotheker in Verbindung.Es vor direkter Belastung durch Licht, Hitze und Feuchtigkeit schützen.Amyl- oder Butylnitrit enthalten; sowie Alphablockierer Arzneimitteln; andere Medikationen gegen Impotenz; Bestimmte Medikamente gegen Bluthochdruck, etc.

Sie müssen mit Ihrem Doktor sofort in Verbindung treten oder mit einem emergency Gesundheitszentrum in Verbindung treten, wenn Sie eine Überdosis vermuten.Nehmen Sie Viagra Oral Jelly nicht öfter als einmal täglich.Symptome für die Überdosierung können wie folgt sein: Brustschmerzen, Übelkeit, unregelmäßiger Herzschlag, Ohnmacht.Wenn Sie denken, Sie haben zu viel Medizin eingenommen, treten sofort mit Ihrem Arzt in Verbindung!Sildenafil verwendet man für die Behandlung der Funktionsstörung (Machtlosigkeit) bei den Männern, sowie bei dem arteriellen Lungenbluthochdruck.Kontraindikationen Viagra Oral Jelly ist für jene Patienten nicht angezeigt, die eine andere Medizin gegen Impotenz einnehmen oder Nitrate haltige Arzneien gegen Brustschmerzen oder Herzprobleme verwenden.Das wirkt auf die Entspannung der glatten Muskeln mit der Benutzung von Stickstoffoxid, einer Chemikalie, die normalerweise die Reaktion für sexuelle Anregung befreit.Diese Medizin sollte nicht von den Frauen und von den Kindern genommen werden, sowie von den Patienten mit einer bekannten Überempfindlichkeit zu irgendeinem Bestandteil der Pille.

[link:kamagrapharma.blogspot.com]

[YOUTUBE=" -CBf8O1tEMo "]sie sucht ihn[/YOUTUBE]

[YOUTUBE] -CBf8O1tEMo[/YOUTUBE]

[YOUTUBE]MeUHkpVgFLk[/YOUTUBE]

[YOUTUBE]HAbLhVuqaC8[/YOUTUBE]

[YOUTUBE="MeUHkpVgFLk"]internet kasino[/YOUTUBE]

[YOUTUBE="HAbLhVuqaC8"]internet kasinoh[/YOUTUBE]

[YOUTUBE]aWIOBTUZ0cM [/YOUTUBE]

[YOUTUBE]yK9zGb5WPn8[/YOUTUBE]

[YOUTUBE="aWIOBTUZ0cM "]internet kasino[/YOUTUBE]

[YOUTUBE="yK9zGb5WPn8"]internet kasinoh[/YOUTUBE]

Jailbreak iphone

single single

Kredit ohne Schufa

[link:www.beeplog.de]

eskrima.co

[link:eskrima.beepworld.de]

By on 2/3/2011 4:16 PM ()

antivirus manual removal and best antivirus to remove trojan and bleeping computer malware removal uninstall antivirus 2009 or iseries antivirus and forefront antivirus review or running two antivirus programs and advanced antivirus activation or pc antivirus ratings

By on 6/24/2010 4:09 AM ()

I've responded to DeeJay's excellent comments in the addendum to the article above.

By on 5/11/2006 12:24 PM ()

This is fanastic,

1
2
3
4
5
6
7
8
9
10

type mypoint = {x:int ; y:int}
with
  interface System.IComparable with
    member p1.CompareTo(p2:obj) = compare p1.y (p2 :?> mypoint).y
  end
end;;
compare {x=3; y=2} {x=2; y=3};; 
=> -1
{x=3; y=2} < {x=2; y=3};;
=> true

without the custom implementation of IComparable... those results would be +1 and false
So because of this... is there any reason at all to be able to pass in custom comparators?
If there is any gain, is it worth the hassle of more complex implementation over just declaring your comparator when you declare your type?
And in the case where you may want to change the comparision of an existing type... can you not just wrap the type? or inherit from it...
although before I get too carried away here's an example i'm not sure quite how to solve yet.
if i want to do a custom comparator for int's. Say compare them when they are rounded down to the nearest 10...
i can't do
type myint = int
with
interface ....
as you can't augment a type abbreviation
nor can i do

1
2
3
4

type myint =
class
  inherit int ....
as int (Int32) is a sealed type

so maybe in this case i really only can wrap the type or delegate to it in a class.
Comparing to Haskell with it's type classes... it doesn't seem like you'd be much better off in this case, as you can't declare instances of a type class with type abbreviations so you'd have to wrap it in a newtype declaration.
Comparing to SML and OCaml with it's functors... this is where the functors win big. Parameterising code (structures) seems to be an incredibly powerful tool for writing datastructures.

By on 5/11/2006 9:34 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper