April 2006 - Haskell-Cafe

coherence when overlapping?
by william kim 12 Apr '06

12 Apr '06

Hi All, One important property of type class dictionary translation is coherence which basically says that two typing derivations for the same term at the same type in the same environment must be equivalent. This definition is established with the assumption of non-overlapping. In the GHC documentation which describes the extension of overlapping instances, an example similar to the following is given. >class C a where > f:a -> a >instance C Int where > f=e1 >instance C a where > f=e2 > >let g x = f x >in g 1 In this case GHC takes an ¡°incoherent¡± decision by taking the second instance as an instantiation of function f even it is executed with an input of type Int. My question is whether the ¡°incoherence¡± behaviour of overlapping instances is derived from the definition of coherence in the non-overlapping setting? If yes, how is it applicable to rule out the incoherent behaviour? If otherwise, what is the definition of coherence with overlapping instances? Thanks. --william _________________________________________________________________ Find just what you are after with the more precise, more powerful new MSN Search. http://search.msn.com.sg/ Try it now.

2 2

Fundeps: I feel dumb
by Creighton Hogg 12 Apr '06

12 Apr '06

Hi, So I'm trying the fun-deps example from http://www.haskell.org/hawiki/FunDeps and seeing if I can use it, but I can't really get things to work the way I want. The code follows below, and the error I get if I try to multiply 10 <*> (vector 10 [0..9]) is No instance for (MatrixProduct a (Vec b) c) arising from use of `<*>' at <interactive>:1:3-5 Probable fix: add an instance declaration for (MatrixProduct a (Vec b) c) In the definition of `it': it = 10 <*> (vector 10 ([0 .. 9])) import Array -- The elements and the size data Vec a = Vec (Array Int a) Int deriving (Show,Eq) type Matrix a = (Vec (Vec a)) class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c instance (Num a) => MatrixProduct a (Vec a) (Vec a) where (<*>) num (Vec a s) = Vec (fmap (*num) a) s vector n elms = Vec (array (0,n-1) $ zip [0..n-1] elms) n

1 0

Announcing Halfs, a Haskell Filesystem
by Isaac Jones 12 Apr '06

12 Apr '06

Halfs is a filesystem implemented in the functional programming language Haskell. Halfs can be mounted and used like any other Linux filesystem, or used as a library. Halfs is a fork (and a port) of the filesystem developed by Galois Connections. We've created a virtual machine to make using Halfs extremely easy. You don't need an extra partition or a thumb drive, or even Linux (Windows and Mac OS can emulate the virtual machine). For the impatient, go to the quick start: http://hackage.haskell.org/trac/halfs/wiki/QuickStart The Halfs web page is here: http://www.haskell.org/halfs/ Background: In the course of developing a web server for an embedded operating system, Galois Connections had need of a filesystem which was small enough to alter to our needs and written in a high-level language so that we could show certain high assurance properties about its behavior. Since we had already ported the Haskell runtime to this operating system, Haskell was the obvious language of choice. Halfs is a port of our filesystem to Linux, with some modifications. High assurance development is a methodology for creating software systems that meet rigorously-defined specifications with a high degree of confidence. That methodology comprises tools and practices. Its goal is to produce such systems reliably and effectively, with an ordinary degree of developer effort. Haskell is particularly well-suited to high assurance development. It is a high-level, fully-expressive, pure, functional language, with a powerful type system. One of the obligations of high assurance development is the demonstration of strong correspondence between high-level executable models and the eventual implementation. Haskell supports this directly: it can describe systems all the way from high-level executable models through to system implementations. The fact that Haskell is pure comes from its mathematical basis, and means that, by default, a function does not interfere with other functions. The type system is an automatic and scalable proof engine that can encode and enforce desirable properties. Together, these features allow the correctness of complex systems to be established, making Haskell ideal for high assurance development. The question was whether Haskell is well suited as the implementation language for a filesystem, which involves fixed sized buffers, lots of IO, and binary data structures. Though correctness is much more important to us than performance, we hoped that a Haskell filesystem would have acceptable performance, and that writing such low-level code would not be awkward or error-prone. We have developed a filesystem, Halfs, which aims to answer the above questions. One may mount a Halfs filesystem in Linux using the FUSE (Filesystem in Userspace) kernel module. We have created two new monads, FSRead and FSWrite which restrict the IO monad to reading and writing operations respectively. For performance, Halfs uses efficient mutable arrays for block IO, as well as caching for blocks and inodes.

1 0

Ambiguous types for collection keys
by Scott Weeks 12 Apr '06

12 Apr '06

Hello everyone, I've been banging my head against my desk a bit so I figured it's time to ask for help :-) I'm writing an application that persists data to disk. The hard stuff is pretty much done (binary serialisation, etc...) The big stumbling block is that I want users to be able to define their own schemas. This means that the keys for a data store may be Integer, Strings, etc... I have a BTreeIndex type: data BTreeIndex a b = Branch { parentBT :: !BlockPtr, keysBT :: ![a], kidsBT :: ![BlockPtr] } | Leaf { parentBT :: !BlockPtr, valsBT :: !(LeafMap a b), prevBT :: !PrevLeaf, nextBT :: !NextLeaf } type IdxPS = BTreeIndex PackedString BlockPtr type IdxInt = BTreeIndex Integer BlockPtr When a user queries I have to read the input from IO and then somehow cast the key/index type without angering the type checker. If I omit the following function I get the ominous "Ambiguous type variable a..." error. If I use it I get a complaint that the checker was expecting an Integer rather than a PackedString. coerceIndex f (Schema _ SInt SPtr _) (r,hdl,o,hdr) = f (r::IdxInt,hdl,o,hdr) coerceIndex f (Schema _ SStr SPtr _) (r,hdl,o,hdr) = f (r::IdxPS,hdl,o,hdr) Where f is a curried select function (e.g. selectAll, selectByKey, etc...) waiting for the final tuple containing the index and other miscellanea that is needed to read the data. I'm hopelessly lost and I assume that the many brilliant minds on this list will chuckle, pat me on the head and tell me what I've been doing wrong. Thanks for your time guys, Scott

4 7

accurately scheduling events
by Henning Thielemann 11 Apr '06

11 Apr '06

I try to schedule musical events and this shall happen quite accurately. I found 'usleep' which is limited to Posix and I cannot interrupt with Ctrl-C if IO actions are scheduled using this function. Then I found 'threadDelay' which can be interrupted, but it is stated that its resolution is 1/50 seconds, which is too coarse. Additionally I found that it liberally rounds the waiting time up to the next multiple of 1/50 second. Even 'threadDelay 0' waits some time. This might be due to the fact that threadDelay was not intended for such applications, but it shall wait at least the time specified: http://www.haskell.org/pipermail/glasgow-haskell-users/2004-January/006148.… My question: Is there some more accurate time scheduling available? Maybe not only a more accurate 'wait' function but a function which processes a list of events and starts the actions at the appropriate time points. When I write do action0 threadDelay t action1 then action1 is not started duration t after action0 is started, but time t after action0 is finished. This should be avoided by a sophisticated scheduling function. This is how I currently employ threadDelay: http://cvs.haskell.org/darcs/haskore/src/Haskore/Basic/Schedule.lhs

3 3

Re: [Haskell-cafe] web servers
by Tim Newsham 10 Apr '06

10 Apr '06

> There's this link: http://www.mdstud.chalmers.se/~md9ms/hws-wp/ Yes there is, but its a broken link. I tried mailing the author and got no response. > From memory I think there may have been a more recent version at > scannedinavian.org (possibly only accessible with darcs?), but still a couple > of years with no apparent activity. I'll try to get it from here. Thanks. > If anyone is interested in using it, contributing to it, or picking over > it for use in an existing project, I'll try and find somewhere stable to > host it and change the licence. Feel free to ask questions on what it > does/doesn't do. You'll probably need to, given the documentation ;-) I'd be interested in looking at it, at the least. > Regardless of it's utility, any criticism or advice on the code would be > appreciated. I'm a bit of a haskell noob, so don't expect anything brilliant. > Daniel Tim Newsham http://www.lava.net/~newsham/

1 0

Substitute for records?
by Mattias Bengtsson 10 Apr '06

10 Apr '06

Currently i'm working, together with a friend, on an abstraction (sort of) of HaskellDB for a school-project. Basically we are generating haskell-modules similar to those generated by DBDirect in HaskellDB together with some helpers for the most common queries you'd want to run. HaskellDB has its own record system (HDBRec) and a HaskellDB-query also returns such a record. The accessor-functions for these records can later be found in DatabaseName.TableName.ColumnName.column. These should be imported qualified to avoid name clashes. This is some example code: students <- School.Students.all db mapM_ printStudentId students printStudentId rec = print $ rec!School.Students.Id.column The main problem for me here is this part: rec!School.Students.Name.column where i would rather just write rec!id This isn't possible and the other way is just too messy for my taste. It simply isn't the easy and nice syntax i had hoped for when we started to develop this. Are there any other nice substitutes for HDBRec or normal haskell records that i could use that doesn't make name clashes an issue? Mattias

2 1

Understanding allocation behavior
by David F. Place 10 Apr '06

10 Apr '06

After reading Daniel Fischer's message about trying to use EnumSet in his Sudoku.hs and finding that it was slower when processing a large data set, I decided to do some profiling. I rewrote his solver to use EnumSets and profiled it. The culprit turns out to be the following function which is responsible for 22% of the allocating in the run. Is there a more efficient way to write this function? foldBits :: Bits c => (a -> Int -> a) -> a -> c -> a foldbits _ z 0 = z foldBits f z bs = foldBits' f 0 bs z foldBits' :: Bits c => (a -> Int -> a) -> Int -> c -> a -> a foldBits' f i bs z | bs == 0 = z | otherwise = z' `seq` foldBits' f i' bs' z' where z' | 1 == bs .&. 1 = f z i | otherwise = z i' = i + 1 bs' = bs `shiftR` 1 ps. I was impressed with how hairy DF's algorithm is and I am not really enough interested in Sudoku to spend the time needed to grok it. So, I decided to try an experiment to see if I could restructure it without understanding it very deeply. Step 1. comment out all the type signatures. Step 2. find the main place that I wanted to change from [Int] to (Set Int) Step 3. compile; make obvious edits; repeat until 0 errors I had it running in a few minutes. I can't imagine doing that in any other programming environment! Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

4 12

lambda evaluator in GADT
by paul＠theV.net 10 Apr '06

10 Apr '06

The introduction to GADT usually starts with a little expression evaluator. So I gave it a try, but there are some troubles. A little data type for lambda expression > data E a where > Lit :: a -> E a > App :: E (a -> b) -> E a -> E b > Lam :: Var a -> E b -> E (a -> b) > Val :: Var a -> E a > > data Var a = Var String some sample values > e1 = Lit 1 > plus = Lit (\x y -> x + y) Next, plus' demonstrate a pitfall in my data definition, i.e., the variable introduced by Lam has type forall a . a, which is is too general force a constraint on its occurrances. I wonder if there a way to make it work. > plus' = let v1 = Var "x" > v2 = Var "y" > in Lam v1 (Lam v2 (App (App plus (Val v1)) (Val v2))) evaluation > eval :: E a -> a > eval (Lit x) = x > eval (App f x) = (eval f) (eval x) > eval (Lam (Var v) e) = \x -> eval (sub v (Lit x) e) > eval (Val (Var v)) = undefined substituation > sub :: String -> E b -> E c -> E c > sub v e e1@(Lit x) = e1 > sub v e (App f x) = App (sub v e f) (sub v e x) > sub v e e'@(Lam w'@(Var w) x) = > if v == w then e' > else Lam w' (sub v e x) the above all works fine, except for the following > {-- > sub v e e'@(Val (Var w)) = > if v == w then e > else e' > --} It seems the last case requires a unification of b and c, which is simply too strong for other cases. What should I do here? Instead of substituting on term level, an alternative way to implement eval is to use an environment to map variables to its values, but that requires all expression values to have a uniform type, which is a conflict to GADT. I'm sure this could be a common issue encountered by GADT beginners, how does one get around it? One solution on top of my head is to use a sum type (or even type class) and stuff every possible value types under it, but that defeats the purpose of using GADT in the first place. Any help is greatly appreciated! Regards, Paul Liu

2 1

Chapter 4 of Hitchhikers Guide to the Haskell is out
by Dmitry Astapov 09 Apr '06

09 Apr '06

Hello, After great amount of procrastination I finally put online the next installment of my Haskell tutorial, which could be found at http://www.haskell.org/haskellwiki/Hitchhikers_Guide_to_the_Haskell Many thanks to all who commented on my efforst, spell-checked the text and urged me to go forward. As alway I'm interested in any feedback. -- Dmitry Astapov //ADEpt GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D

1 0