I am going over ternary tree library and it all looks clear to me with exception of the method below. Could you please explain to me how to read this: data TernarySet a = Node !a !(TernarySet a) !(TernarySet a) !(TernarySet a) | Null !(TernarySet a) | End deriving (Show, Eq) instance Binary a => Binary (TernarySet a) where ...... skipped get = do ---first call to get tag <- getWord8 case tag of _ | tag < 8 -> do ch <- get --- second call to get l <- if tag `testBit` 2 then get else return End ---third call to get e <- if tag `testBit` 1 then get else return End h <- if tag `testBit` 0 then get else return End return (Node ch l e h) 8 -> return (Null End) .......skipped What I don't understand here is recursive(?) call to 'get'. The first 'get' as I understand is an instance implementation of get from Binary module. What is 'ch <- get' (the second call) and 'get' inside 'if tag `testBit` 2 then get ...' (the third call)? tag <- getWord8 reads word8 from monad, then ch <- get reads what (just a copy of tag???)? Is get inside if ..then else statements is a look ahead get calls, to read next word8? Please provide more details if possible. Thanks a lot. Malik
On Wed, Jul 29, 2009 at 4:28 PM, MH
I am going over ternary tree library and it all looks clear to me with exception of the method below.
<cut>
What I don't understand here is recursive(?) call to 'get'. The first 'get' as I understand is an instance implementation of get from Binary module.
get is a method of the Binary typeclass, it is an action in the Get monad. A "Get a" action can be run against a bytestring to transform a binary code into an Haskell value of type a. A Binary instance describe how to encode (with put) to binary records and decode (with get) from binary records a specific type, here "TernarySet a". Here you have the definition of get for a ternary tree, the get inside this definition are call to get for the right type, not always the same, for instance in :
ch <- get
This get is of type "Get a" (of TernarySet _a_), this can be inferred because ch is later used in "Node ch l e h". Similarly l, e and h are determined to be of type "TernarySet a" and so the gets in :
l <- if tag `testBit` 2 then get else return End e <- if tag `testBit` 1 then get else return End h <- if tag `testBit` 0 then get else return End
are of type "Get (TernarySet a)" and so they recursively call the get we're defining (that is no surprise since this type is recursive). getWord8 is one of the primitive provided by Binary, though you could use get instead, it would often be unclear or need a type annotation (like here). If you have experienced the read function, this is the same idea, though a little bit more advanced (one of these things you can't easily do with object : be polymorphic on the return type). Binary can achieve pretty good performances in good cases, sometimes only limited by the speed of your hardware. -- Jedaï
participants (2)
-
Chaddaï Fouché -
MH