- Haskell-Cafe - Haskell.org

Re: Fundeps: I feel dumb
by oleg＠pobox.com 13 Apr '06

13 Apr '06

Creighton Hogg wrote: > 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])) Let us look at the instance class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c instance (Num a) => MatrixProduct a (Vec a) (Vec a) where it defines what happens when multiplying a vector of some numeric type 'a' by a value _of the same_ type. Let us now look at the error message: > (MatrixProduct a (Vec b) c) That is, when trying to compile your expression 10 <*> (vector 10 ([0 .. 9])) the typechecker went looking for (MatrixProduct a (Vec b) c) where the value and the vector have different numeric types. There is no instance for such a general case, hence the error. It is important to remember that the typechecker first infers the most general type for an expression, and then tries to resolve the constraints. In your expression, 10 <*> (vector 10 ([0 .. 9])) we see constants 10, 10, 0, 9. Each constant has the type Num a => a. Within the expression 0 .. 9, both 0 and 9 must be of the same type (because [n .. m] is an abbreviation for enumFromThen n m, and according to the type of the latter enumFromThen :: a -> a -> [a] both arguments must be of the same type). But there is nothing that says that the first occurrence of 10 must be of the same numeric type as the occurrence of 9. So, the most general type assignment will be (Num a => a) for 10, and (Num b => b) for 9. Solution: either choose a specific (non-polymorphic type) > test1 = (10::Int) <*> (vector 10 [0..9::Int]) Or tell the typechecker that those constants must be of the same type: > test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)])

2 1

Counting bits: Sanity Check
by David F. Place 13 Apr '06

13 Apr '06

Hi All, Since it seems that real applications need more than just union, intersection, difference and complement to be fast to make EnumSet useful, I've been looking into the less naive approaches to the other things. In particular, size seems to find itself in the inner loop. I've made a comparison of various approaches to bit counting. It seems I was too hasty to declare Bulat's suggestion of table lookup (table,table32) the winner. It seems Robert's suggestion of Kernighan's (kern) method is faster. I also implemented the method described in pages 187-188 of Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors. (ones32) It's slower on my powerbook, but may be the winner on 64bit processors. Here are the results: [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 ones32 21 1.788u 0.136s 0:03.30 57.8% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table 21 2.404u 0.164s 0:04.96 51.6% 0+0k 0+1io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table32 21 2.067u 0.140s 0:04.27 51.5% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 kern 21 1.729u 0.137s 0:03.25 56.9% 0+0k 0+1io 0pf+0w If you'd like to give it a whirl on your fancy modern computers, here's the code: ghc -O3 -optc-O3 -o bits BitTwiddle.hs Of course, if I've done something lame-brained and skewed the results, please let me know. Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

4 6

The Marriage of Heaven and Hell: Type Classes and Bit-Twiddling
by David F. Place 13 Apr '06

13 Apr '06

Hi: Looking around further for a charming way to count bits, I found a method that is completely inscrutable might be very fast. http://graphics.stanford.edu/~seander/bithacks.html Counting bits set in 12, 24, or 32-bit words using 64-bit instructions I thought it would be neat to have size function constrained to members of Bounded that would automatically choose which method depending on the extent of the domain of the set. So, a small set could be computed by the very fast method and the compiler would be able to do the dispatch as part of constant folding. This is what I came up with. It works, but it seems kind of forced. I wonder if there is a better way. sizeB :: (Bounded a,Enum a) => a -> Set a -> Int sizeB e = case fromEnum $ maxBound `asTypeOf` e of x | x <= 12 -> \(Set w) -> fromIntegral $ c12 $ fromIntegral w x | x <= 24 -> \(Set w) -> fromIntegral $ c24 $ fromIntegral w x | x <= 32 -> \(Set w) -> fromIntegral $ c32 $ fromIntegral w _ -> \(Set w) -> bitcount 0 w c12 :: Word64 -> Word64 c12 v = (v * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f c24' :: Word64 -> Word64 c24' v = ((v .&. 0xfff) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f c24 :: Word64 -> Word64 c24 v = (c24' v) + ((((v .&. 0xfff000) `shiftR` 12) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f) c32 :: Word64 -> Word64 c32 v = (c24 v) + (((v `shiftR` 24) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f) For example: data Test1 = Foo | Bar | Baaz | Quux deriving (Enum, Bounded) sizeTest1 :: (Set Test1) -> Int sizeTest1 = sizeB Foo Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

1 1

Re: coherence when overlapping?
by oleg＠pobox.com 13 Apr '06

13 Apr '06

It seems that the subject is a bit more complex, and one can force GHC to choose the less specific instance (if one confuses GHC well enough): see the example below. First of all, the inequality constraint is already achievable in Haskell now: "TypeEq t1 t2 False" is such a constraint. One can write polymorphic functions that distinguish if the argument a list (any list of something) or not, etc. One can write stronger invariants like records where labels are guaranteed to be unique. There are two problems: first there are several notions of type inequality, all of which are useful in different circumstances. http://www.haskell.org/pipermail/haskell-prime/2006-March/000936.html Second, how inequality interacts with functional dependencies -- and in general, with the type improvement. And here, many interesting things emerge. For example, the following code > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > {-# OPTIONS -fallow-overlapping-instances #-} > > module Foo1 where > > class C a b | a -> b where > f :: a -> b > > instance C Int Bool where > f x = True > > instance TypeCast Int b => C a b where > f x = typeCast (100::Int) > > class TypeCast a b | a -> b, b->a where typeCast :: a -> b > class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b > class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b > instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x > instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' > instance TypeCast'' () a a where typeCast'' _ x = x > > class D a b | a -> b where > g :: a -> b > > instance D Bool Bool where > g x = not x > > instance TypeCast a b => D a b where > g x = typeCast x > > test1 = f (42::Int) -- ==> True > test2 = f 'a' -- ==> 100 > > test3 = g (1::Int) -- ==> 1 > test4 = g True -- ==> False > > bar x = g (f x) `asTypeOf` x We see that test1 through test4 behave as expected. We can even define the function 'bar'. It's inferred type is *Foo1> :t bar bar :: (C a b, D b a) => a -> a The question becomes: is this a function? Can it be applied to anything at all? If we apply it to Int (thus instantiating the type a to Int), the type b is instantiated to Bool, and so (following the functional dependency for class D), the type a should be Bool (and it is already an Int). OTH, if we apply bar to anything but Int, then the type b should be Int, and so should the type a. Liar's paradox. And indeed, bar cannot be applied to anything because the constraints are contradictory. What is more interesting is the slight variation of that example: > class C a b | a -> b where > f :: a -> b > > instance C Int Int where > f x = 10+x > > instance TypeCast a b => C a b where > f x = typeCast x > > class D a b | a -> b where > g :: a -> b > > instance D Int Bool where > g x = True > > instance TypeCast Int b => D a b where > g x = typeCast (10::Int) > > test1 = f (42::Int) > test2 = f 'a' > > test3 = g (1::Int) > test4 = g True > > bar x = g (f x) `asTypeOf` x > > test5 = bar (1::Int) *Foo> :t bar bar :: (C a b, D b a) => a -> a If bar is applied to an Int, then the type b should be an Int, so the first instance of D ought to have been chosen, which gives the contradiction a = Bool. And yet it works (GHC 6.4.1). Test5 is accepted and even works *Foo> test5 10

2 1

coherence when overlapping?
by william kim 13 Apr '06

13 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 13 Apr '06

13 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 11 Apr '06

11 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