[Haskell-cafe] Ambiguous types for collection keys
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] coherence when overlapping?
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] web servers
I'm interested, but I don't have the time to look right now (or in the next couple of months, as far as I can see). What would really interest me is a system that can provide the functionality of the Python packages I currently use (TurboGears [1], of which the web server/controller component is CherryPy [2]). There's also some interesting recent CherryPy-related discussion about web dispatching that I think could translate very well to Haskell [3][4]. ... I'd also be interested in a system that handled overlapped asynchronous requests in a fashion not dissimilar to Twisted [5]. I've very recently been playing with Twisted as a way to deal with large numbers of overlapping lightweight requests without having large numbers of active threads. Twisted requires one to string together asynchronous callbacks to assemble a process that completes over time. It seems to me that the sequencing of asynchronous operations is very much like threading computations in a monad, and that the higher-order functions on monads could also be used for composition of asynchronous operations. I just implemented a sequence function for Twisted operations whose implementation started to feel very like foldr. This can't be new, and I'm wondering if there is any interesting work out there on using monads for multiple asynchronous I/O operations. (And, much as I'd love to use Haskell for this, is there work that would translate cleanly to Python?) #g -- [1] http://www.turbogears.com/ [2] http://www.cherrypy.org/ [3] http://pythonpaste.org/do-it-yourself-framework.html (cf. descriptions of object publishing) [4] The above link was posted in this discussion thread: http://groups.google.com/group/cherrypy-users/browse_frm/thread/47035d8d78adad69/bf02b489e45ce6c5?tvc=1hl=en#bf02b489e45ce6c5 [5] http://twistedmatrix.com/ http://twistedmatrix.com/projects/core/ Daniel McAllansmith wrote: Following is a message I sent yesterday, sans attachment. Looks like the code was too bloated to get through under the list size limit. As I say in the original message , I'm keen for any feedback. So let me know if anyone wants the actual code (20 KB, compressed) to have a look through. Cheerio Daniel On Sunday 09 April 2006 06:24, Tim Newsham wrote: I found a copy of Simon Marlow's HWS on haskell.org's cvs server. I know there's a newer plugin version, but I cant find a working link to the actual code. There's this link: http://www.mdstud.chalmers.se/~md9ms/hws-wp/ 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. Besides HWS, what other web servers exist? Does anyone actually use a haskell based web server in practice? Which web server is considered the most mature? stable? fastest? I'm trying to decided if I should sink some time into HWS or if I should use another server. Several months ago I had a bit of play-time available which I spent on writing a HTTP server in Haskell. The goal was a HTTP 1.1 compliant server that could be embedded in a Haskell app, be reconfigured on the fly and have different request handlers added/removed. I did have a quick look at HWS before I started but I seem to recall it was pretty basic (in terms of the amount of the HTTP spec. implemented). In any event, I started from scratch. It's certainly not finished, and it's the very first thing I wrote with Haskell so it's a bit of a dogs breakfast, but it might be of interest. There's lots that needs doing but it should just be a case of writing a request handler to get it doing _something_ useful. It's always been my intention to get back to it, clean it up a bit/lot and release it under a more liberal licence (currently 'all rights reserved'), but have had little time available. Eventually I hope to actually use it in anger. 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 ;-) Regardless of it's utility, any criticism or advice on the code would be appreciated. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Graham Klyne For email: http://www.ninebynine.org/#Contact ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
On 4/12/06, Scott Weeks [EMAIL PROTECTED] wrote: Hello everyone, I've been banging my head against my desk a bit so I figured it's time to ask for help :-) 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. Well, if you get an ambiguous type variable error, you probably (I think) need to add some type annotations. For example: class Foo a where foo :: a bar :: a - String Evaluating bar foo will result in an error, but bar (foo :: Integer) will work just fine. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Counting bits: Sanity Check
On Apr 11, 2006, at 10:09 AM, David F. Place wrote: 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 200 300 ones32 21 1.788u 0.136s 0:03.30 57.8% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 200 300 table 21 2.404u 0.164s 0:04.96 51.6% 0+0k 0+1io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 200 300 table32 21 2.067u 0.140s 0:04.27 51.5% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 200 300 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: BitTwiddle.hs ghc -O3 -optc-O3 -o bits BitTwiddle.hs I get similar results on my machine (PPC powerbook). 'ones32' barely edges out 'kern' and 'table' and 'table32' come in behind. Average 'user' time over three runs: ones32: 0.540s kern: 0.545s table: 0.730s table32: 0.632s Of course, if I've done something lame-brained and skewed the results, please let me know. Cheers, David David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] coherence when 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.
No it doesn't (ghc 6.4.1). I've just tried it. It uses the C Int instance,
for exactly the reason you describe.
There is a flag -fallow-incoherent-instances that _does_ allow incoherence
Simon
{-# OPTIONS -fallow-overlapping-instances -fglasgow-exts
-fallow-undecidable-instances #-}
module Main where
class C a where
f::a - a
instance C Int where
f x = x+1
instance C a where
f x = x
main = print (let g x = f x
in g (1::Int))
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
Well, if you get an ambiguous type variable error, you probably (I think) need to add some type annotations. For example: class Foo a where foo :: a bar :: a - String Evaluating bar foo will result in an error, but bar (foo :: Integer) will work just fine. The problem is that I get an incoming value which is a key of some sort. There's no way of knowing what type that value is supposed to be until I compare it with the schema from the above example. where I _am_ adding type annotations. 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) When I try to add type annotations I get a complaint from the typechecker that says (In the case of the above example) Expected type: Integer, Inferred Type: PackedString. Is the alternative to write different select methods for each key type (selectInt, selectPS, ...)? God I hope not, that would be a bit scary. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
On Apr 12, 2006, at 3:18 PM, Scott Weeks wrote: Well, if you get an ambiguous type variable error, you probably (I think) need to add some type annotations. For example: class Foo a where foo :: a bar :: a - String Evaluating bar foo will result in an error, but bar (foo :: Integer) will work just fine. The problem is that I get an incoming value which is a key of some sort. There's no way of knowing what type that value is supposed to be until I compare it with the schema from the above example. where I _am_ adding type annotations. 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) When I try to add type annotations I get a complaint from the typechecker that says (In the case of the above example) Expected type: Integer, Inferred Type: PackedString. Is the alternative to write different select methods for each key type (selectInt, selectPS, ...)? God I hope not, that would be a bit scary. I'm not 100% sure I understand your use case, but I think you might be able to crack this by using Data.Dynamic: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data- Dynamic.html Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Counting bits: Sanity Check
On Wednesday 12 April 2006 02:09, David F. Place wrote: If you'd like to give it a whirl on your fancy modern computers, Averages of user time for three runs on an Athlon64 running 64bit linux: kern0.29700 ones32 0.30733 table32 0.37333 table 0.38400 I ran a whole lot more of kern and ones32... kern was consistently faster than ones32. Curious. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
Robert Dockins wrote: On Apr 12, 2006, at 3:18 PM, Scott Weeks wrote: Well, if you get an ambiguous type variable error, you probably (I think) need to add some type annotations. For example: class Foo a where foo :: a bar :: a - String Evaluating bar foo will result in an error, but bar (foo :: Integer) will work just fine. The problem is that I get an incoming value which is a key of some sort. There's no way of knowing what type that value is supposed to be until I compare it with the schema from the above example. where I _am_ adding type annotations. 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) When I try to add type annotations I get a complaint from the typechecker that says (In the case of the above example) Expected type: Integer, Inferred Type: PackedString. Is the alternative to write different select methods for each key type (selectInt, selectPS, ...)? God I hope not, that would be a bit scary. I'm not 100% sure I understand your use case, but I think you might be able to crack this by using Data.Dynamic: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data- Dynamic.html Or carry an instance in along with a type parameter, using existentials or GADT. Brandon Moore ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
Or carry an instance in along with a type parameter, using existentials or GADT. Brandon Moore Do you know of an example that would apply to my situation? I think I neglected to state part of my problem. I am storing the root nodes of btree indexes in a heterogeneous list using Typeable. When they come out of the list they need to be unwrapped I think this will clarify my situation because I've been doing a poor job of explaining: import Data.Dynamic data Foo a = FVal a deriving (Show, Typeable) type FooStr = Foo String type FooInt = Foo Integer main = do fooType - getLine fooVal - getLine let foo = toDyn (FVal fooVal) fs= [foo] (f:_) = fs Just dynFoo = fromDynamic f dostuff dynFoo dostuff :: (Show a) = Foo a - IO () dostuff (FVal x) = print x This fails with: Ambiguous type variable `a' in the constraints: `Typeable a' arising from use of `fromDynamic' at /Users/weeksie/workspace/haskell/Main.hs:243:20-30 `Show a' arising from use of `dostuff' at /Users/weeksie/workspace/haskell/Main.hs:247:2-8 Probable fix: add a type signature that fixes these type variable(s) However, changing main: main = do fooType - getLine fooVal - getLine let foo = toDyn (FVal fooVal) fs= [foo] (f:_) = fs Just dynFoo = fromDynamic f if fooType == str then dostuff (dynFoo::FooStr) else dostuff (dynFoo::FooInt) Fails with: Couldn't match `Integer' against `String' Expected type: FooInt Inferred type: FooStr In the expression: dynFoo :: FooInt In the first argument of `dostuff', namely `(dynFoo :: FooInt)' I'm probably going about this in the wrong way. I'd love some advice on how to either do it better or weave some Type Magic to achieve the same effect. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Counting bits: Sanity Check
On Apr 12, 2006, at 3:30 PM, Daniel McAllansmith wrote: Averages of user time for three runs on an Athlon64 running 64bit linux: kern0.29700 ones32 0.30733 table32 0.37333 table 0.38400 I ran a whole lot more of kern and ones32... kern was consistently faster than ones32. Curious. Yes, especially curious since the algorithm is taken from AMD's optimization guide for the Athlon and Opteron series. I'm not good enough at reading core syntax to be able to see what GHC is doing with it. I wonder how this other crazy algorithm I found will work on your 64 bit omputer. It is much slower on my 32 bit PPC powerbook for obvious reasons. If you'd like to try it, I'll include an updated BitTwiddle.hs . Usage: time ./bits 200 300 64 BitTwiddle.hs Description: Binary data David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
On Apr 12, 2006, at 4:09 PM, Scott Weeks wrote:
Or carry an instance in along with a type parameter, using
existentials or GADT.
Brandon Moore
Do you know of an example that would apply to my situation?
I think I neglected to state part of my problem. I am storing the
root nodes of btree indexes in a heterogeneous list using Typeable.
When they come out of the list they need to be unwrapped
I think this will clarify my situation because I've been doing a
poor job of explaining:
import Data.Dynamic
data Foo a = FVal a
deriving (Show, Typeable)
type FooStr = Foo String
type FooInt = Foo Integer
main = do
fooType - getLine
fooVal - getLine
let foo = toDyn (FVal fooVal)
fs= [foo]
(f:_) = fs
Just dynFoo = fromDynamic f
dostuff dynFoo
dostuff :: (Show a) = Foo a - IO ()
dostuff (FVal x) = print x
This fails with:
Ambiguous type variable `a' in the constraints:
`Typeable a'
arising from use of `fromDynamic' at /Users/weeksie/workspace/
haskell/Main.hs:243:20-30
`Show a'
arising from use of `dostuff' at /Users/weeksie/workspace/haskell/
Main.hs:247:2-8
Probable fix: add a type signature that fixes these type
variable(s)
However, changing main:
main = do
fooType - getLine
fooVal - getLine
let foo = toDyn (FVal fooVal)
fs= [foo]
(f:_) = fs
Just dynFoo = fromDynamic f
if fooType == str
then dostuff (dynFoo::FooStr)
else dostuff (dynFoo::FooInt)
You are trying to assign two distinct types to dynFoo; that's a no-
no. You need to move the usage of the polymorphic function out of
the let so that the use at each distinct type doesn't get unified.
{-# OPTIONS -fglasgow-exts #-}
import Data.Dynamic
data Foo a = FVal a
deriving (Show, Typeable)
type FooStr = Foo String
type FooInt = Foo Integer
main = do
fooType - getLine
fooVal - getLine
let foo = toDyn (FVal fooVal)
fs= [foo]
(f:_) = fs
if fooType == str
then dostuff (fromDyn f undefined :: Foo String)
else dostuff (fromDyn f undefined :: Foo Int)
dostuff :: (Show a) = Foo a - IO ()
dostuff (FVal x) = print x
BTW, this little example always stuffs a string into the FVal, so
trying to get anything else out will fail.
Rob Dockins
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Counting bits: Sanity Check
On Thursday 13 April 2006 08:55, David F. Place wrote: On Apr 12, 2006, at 3:30 PM, Daniel McAllansmith wrote: Averages of user time for three runs on an Athlon64 running 64bit linux: kern0.29700 ones32 0.30733 table32 0.37333 table 0.38400 I ran a whole lot more of kern and ones32... kern was consistently faster than ones32. Curious. Yes, especially curious since the algorithm is taken from AMD's optimization guide for the Athlon and Opteron series. I'm not good enough at reading core syntax to be able to see what GHC is doing with it. I wonder how this other crazy algorithm I found will work on your 64 bit omputer. It is much slower on my 32 bit PPC powerbook for obvious reasons. If you'd like to try it, I'll include an updated BitTwiddle.hs . Usage: time ./bits 200 300 64 Averages of user time of five runs on an Athlon64 running 64bit linux: 64 0.1974 kern0.2980 ones32 0.3240 table32 0.3754 table 0.3798 64 looks to be a good bit faster. You didn't change anything in the ones32 algorithm did you? The other algorithms are taking roughly what they did last time, but ones32 seems consistently slower now. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Counting bits: Sanity Check
On Apr 12, 2006, at 5:21 PM, Daniel McAllansmith wrote: Averages of user time of five runs on an Athlon64 running 64bit linux: 64 0.1974 kern0.2980 ones32 0.3240 table32 0.3754 table 0.3798 64 looks to be a good bit faster. You didn't change anything in the ones32 algorithm did you? The other algorithms are taking roughly what they did last time, but ones32 seems consistently slower now. Thanks for running it. Looks like 64 is worth the trouble. If the 32 bit wide algorithm is so fast, the 12 bit wide one must be blazingly fast. (See my other thread The Marriage of Heaven and Hell.) I didn't make any changes to ones32 according to diff. Cheers, David David F. Place mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Ambiguous types for collection keys
You are trying to assign two distinct types to dynFoo; that's a no-no.
You need to move the usage of the polymorphic function out of the let
so that the use at each distinct type doesn't get unified.
{-# OPTIONS -fglasgow-exts #-}
import Data.Dynamic
data Foo a = FVal a
deriving (Show, Typeable)
type FooStr = Foo String
type FooInt = Foo Integer
main = do
fooType - getLine
fooVal - getLine
let foo = toDyn (FVal fooVal)
fs= [foo]
(f:_) = fs
if fooType == str
then dostuff (fromDyn f undefined :: Foo String)
else dostuff (fromDyn f undefined :: Foo Int)
dostuff :: (Show a) = Foo a - IO ()
dostuff (FVal x) = print x
BTW, this little example always stuffs a string into the FVal, so
trying to get anything else out will fail.
Thanks for the example it makes a bit of sense now, I really appreciate
you taking the time to help me on this.
Cheers,
Scott
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] web servers
On Wednesday 12 April 2006 22:52, Graham Klyne wrote: I'm interested, but I don't have the time to look right now (or in the next couple of months, as far as I can see). What would really interest me is a system that can provide the functionality of the Python packages I currently use (TurboGears [1], of which the web server/controller component is CherryPy [2]). There's also some interesting recent CherryPy-related discussion about web dispatching that I think could translate very well to Haskell [3][4]. It's certainly nothing that grand. It's intended scope was confined to accepting connections, decoding requests and handing them off to arbitrary request handlers which is where all that higher level stuff would come into play. I just had a look at Network.HTTP, looks like there have been some recent changes to allow server-side uses. Perhaps that could be a home for parts of it, though the two approaches seem a bit different. Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Announcing Halfs, a Haskell Filesystem
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fundeps: I feel dumb
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] coherence when overlapping?
Thank you Simon.
But I am still confused by the exact definition of coherence in the case of
overlapping. Does the standard coherence theorem apply? If yes, how? If no,
is there a theorem?
Is there any write-up on this?
Thanks.
--william
From: Simon Peyton-Jones [EMAIL PROTECTED]
To: william kim [EMAIL PROTECTED],haskell-cafe@haskell.org
Subject: RE: [Haskell-cafe] coherence when overlapping?
Date: Wed, 12 Apr 2006 17:43:33 +0100
| 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.
No it doesn't (ghc 6.4.1). I've just tried it. It uses the C Int
instance, for exactly the reason you describe.
There is a flag -fallow-incoherent-instances that _does_ allow incoherence
Simon
{-# OPTIONS -fallow-overlapping-instances -fglasgow-exts
-fallow-undecidable-instances #-}
module Main where
class C a where
f::a - a
instance C Int where
f x = x+1
instance C a where
f x = x
main = print (let g x = f x
in g (1::Int))
_
Download MSN Messenger emoticons and display pictures.
http://ilovemessenger.msn.com/?mkt=en-sg
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fundeps: I feel dumb
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)]) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: coherence when overlapping?
But I am still confused by the exact definition of coherence in the case of overlapping. Does the standard coherence theorem apply? If yes, how? If no, is there a theorem? Yes, the is, by Martin Sulzmann et al, the Theory of overloading (the journal version) http://www.comp.nus.edu.sg/~sulzmann/ms_bib.html#overloading-journal A simple intuition is this: instance selection may produce more than one candidate instance. Having inferred a polymorphic type with constraints, the compiler checks to see of some of the constraints can be reduced. If an instance selection produces no candidate instances, the typechecking failure is reported. If there is exactly one candidate instance, it is selected and the constraint is removed because it is resolved. An instance selection may produce more then one candidate instance. Those candidate instances may be incomparable: for example, given the constraint C a and instances C Int and C Bool, both instances are candidates. If such is the case, the resolution of that constraint is deferred and it `floats out', to be incorporated into the type of the parent expression, etc. In the presence of overlapping instances, the multiple candidate instances may be comparable, e.g. C a and C Int. The compiler then checks to see if the target type is at least as specific as the most specific of those candidate instances. If so, the constraint is reduced; otherwise, it is deferred. Eventually enough type information is available to reduce all constraints (or else it is a type error). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
