Re: [Haskell-cafe] Class invariants/laws
Just today I was looking at the implementation of Arrows and noticed this:
{-# RULES
compose/arr forall f g .
arr f arr g = arr (f g)
... other rules ...
#-}
But consider this Arrow:
newtype (a : b) = LA2 { runLA2 :: [a] - [b] }
instance Arrow (:) where
arr = LA2 . map
LA2 ab LA2 bc = LA2 $ \la -
let dupe [] = []
dupe (x:xs) = (x : x : dupe xs)
lb = dupe (ab la)
in bc lb
first (LA2 f) = LA2 $ \l - let (as,bs) = unzip l in zip (f as) bs
runLA2 (arr (+1) arr (+1)) [1,2,3]
= [3,3,4,4,5,5]
runLA2 (arr ((+1) (+1))) [1,2,3]
= [3,4,5]
Now, the RULE clearly states one of the arrow laws, so it's sound for
any real Arrow, and : is clearly not a real Arrow. But, :
satisfies the compiles restriction and breaks the validity of the
RULE.
-- ryan
On 10/18/07, Simon Peyton-Jones [EMAIL PROTECTED] wrote:
| These invariants are basically impossible to enforce by the compiler,
| but nonetheless certain classes have laws which are expected to hold,
| and I would not be surprised if (for example) GHC optimization RULES
| depended on them.
|
| I, in fact, would be surprised if there were such dependencies. (Not
| that there might not be good reasons to want to rely on such laws for
| some conceivable optimization, I just doubt that any implementation
| actually does.)
|
| Simon?
I don't believe GHC relies on any class laws. It'd be pretty dangerous to do
so, I think.
Simon
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] ANNOUNCE: Lazy SmallCheck 0.1
That's pretty cool. If you are not yet aware of it, you might want to compare this with the EasyCheck library for Curry. They directly use functional logic programming for test generation, where you use exceptions for simulating logical variables. Here are some slides of a talk I heard recently: http://www.informatik.uni-kiel.de/~jac/data/DarkSecret.pdf (in German, unfortunately) Matthew Naylor wrote: Announcing Lazy SmallCheck 0.1, a library for exhaustive, demand-driven testing of Haskell programs. Lazy SmallCheck is based on the idea that if a property holds for a partially-defined input then it must also hold for all fully-defined instantiations of that input. Compared to `eager' input generation in SmallCheck, Lazy SmallCheck may require significantly fewer test-cases to verify a property for all inputs up to a given depth. There is a webpage for Lazy SmallCheck: http://www-users.cs.york.ac.uk/~mfn/lazysmallcheck/ There you'll find a more detailed description, a worked example, a comparison with SmallCheck on a number of benchmarks, and link to download the library. The library was developed together with Fredrik Lindblad during his recent visits to York. Suggestions, experiences and bug reports are welcome! Matthew. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] data Bin = Zero | One
To convert to and from integrals you could define two functions: binToNum :: Num a = Bin - a binToNum Zero = 0 binToNum One = 1 numToBin :: Num a = a - Bin numToBin 0 = Zero numToBin _ = One Or you could derive Enum for your Bin type. This wil automatically associate integers with the constructors of your type, in the order given. (See section 10.2 of the haskell report: http://www.haskell.org/onlinereport/derived.html) data Bin = Zero | One deriving Enum fromEnum Zero 0 fromEnum One 1 If this is not what you want, could you specify more precisely what difficulty you ran into? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic file closing after readFile
On Fri, Oct 19, 2007 at 02:09:01 +1000, Matthew Brecknell wrote: Magnus Therning: Just out of curiosity, how would I go about finding this myself? (Ideally it'd be an answer other than read the source for the libraries you are using. :-) Well, I can at least try to expand a little on read the source. :-) You'll first need a solid understanding of lazy evaluation in the context of pure computations. Read about normal evaluation order, WHNF (weak head normal form), and which contexts force WHNF. Use pen and paper to manually derive the evaluation order for some pure computations of your choice (folds over infinite lists would be a good start). Experiment with seq. Experiment with the various causes of stack overflows. Next, understand that while the IO monad is quite strict about sequencing actions, its return is not strict in its argument. Observe that the combinators in Control.Monad generally do not force returned computations. Browse the source of GHC's IO library to understand how it sequences IO actions. Read the source for unsafePerformIO and unsafeInterleaveIO to understand how and for what purposes they allow you to break that sequencing. Next, read the source for hGetContents. After all that, you should be a little better equipped to diagnose problems with lazy IO! I'll certainly try to look into all of that. However, I suspect your suggestion doesn't scale very well. On my original code it's easy, it was less than 10 lines, but how do I know where to start looking if it's a program of 100 lines, or 1000 lines? The problem could occur in an updated library that I just use... Well you get the idea :-) I can use profiling to find where time and space is spent. But what about other finite resources that my program uses, such as file handles? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus．therning＠gmail．com http://therning.org/magnus signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Polymorphic (typeclass) values in a list?
Why is it illegal to store values of differing types, but which
instance the same class, into a list? e.g.
a = [ 1, 2.0 ] :: Num a = [a]
After all, sometimes all you need to know about a list is that all the
elements support a common set of operations. If I'm implementing a 3d
renderer for example, I'd like to have
class Renderable a where
render :: a - RasterImage
scene :: Renderable a = [a]
Instead of hardcoding a bunch of types as being Renderable, as in
data Renderable
= Point Something
| Line Something
| Polygon Something
scene :: [Renderable]
Or maybe
data Point = Point Something
data Line = Line Something
data Polygon = Polygon Something
scene :: { points :: [Point], lines :: [Line], polygons :: [Polygons] }
Is there a way of achieving what I want to do? Existentials maybe? I'm
still learning the basic stuff and don't grok existentials at all, but
I even if I use those, I'll still have to wrap things up in a
constructor, won't I?
Thanks a bunch,
TJ
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
Henning Thielemann [EMAIL PROTECTED] writes: Most proofs in mathematics use intuitive arguments, most proofs are not formalized enough in order to be checked by machines. Ok, this can be considered a deficiency of machine provers. But in the history there were famous proofs which turned out to be wrong. Remember the first proof of the four color theorem of Alfred Kempe (cited from, you guess it, wikipedia :-) http://en.wikipedia.org/wiki/Four_color_theorem ) Or remember the first trial of Andrew Wile to prove the Taniyama-Shimura-Weil conjecture for Fermat's last theorem. It is generally hard to show that a proof is incorrect if the statement is correct. You completely misunderstand the goal and nature of Wikipedia. The goal is not truth, but verifiability. It is not Wikipedia's job to determine whether a mathematical proof is correct, but merely if it is accepted by the mathematical community. Truth has absolutely nothing to do with it. Wikipedia is a source-based encyclopedia, and when executed properly, its articles will reflect the biases of its sources. This should be mainstream, learned opinion in the field. See http://en.wikipedia.org/wiki/WP:V -- Doug Quale ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hiding side effects in a data structure
While thinking about how to generate unique integer IDs on demand without using
a state variable, I came up with an interesting design pattern. It's a way of
doing side-effecting computation outside IO. Referential transparency is
preserved by making the side effects spatial rather than temporal: by hiding
side effects behind lazy thunks in a data structure, they can be disguised as
the output of a single, apparently nondeterministic IO function used to data
structure. This lets pure code use nondeterministic computation without the
monadic plumbing required to maintain state.
The getContents function works this way, but I came up with a more interesting
example. The code below is a source of unique integer IDs that is modeled
after the RandomGen class. It uses unsafeInterleaveIO under the hood,
preserving referential transparency but not determinism.
It seems to work. However, I'm not entirely sure how safe my use of
unsafeInterleaveIO is. In particular, could the two branches of the tree get
CSE'd? I'm also curious what people think about the general design pattern.
module Unique where
import Control.Monad(liftM)
import Data.IORef
import System.IO.Unsafe
-- The goal is to produce an infinite tree of integers where each node in the
-- tree has a unique value.
type Unique = Int
data Supply = Supply Unique Supply Supply
-- The tree can be used in a stateful manner as a source of unique integers.
getUnique :: Supply - (Unique, Supply)
getUnique (Supply u s1 _) = (u, s1)
-- The tree can also be split into independent sources of unique integers.
split :: Supply - (Supply, Supply)
split (Supply _ s1 s2) = (s1, s2)
-- The catch is, the tree will probably be visited very sparsely, with most of
-- it being skipped. Assigning every node its own integer is very bad, because
-- that will waste most of the 2^32 available integers very quickly. In fact,
-- it can get used up in just 32 calls to getUnique.
--
-- Instead, we'll create a tree where integers magically appear only in places
-- where they are actually used.
-- First, we need an IO-bound supply of integers.
newtype IOSupply = IOSupply (IORef Unique)
newIOSupply :: IO IOSupply
newIOSupply = liftM IOSupply $ newIORef 0
getUniqueIO :: IOSupply - IO Unique
getUniqueIO (IOSupply s) = do
u - readIORef s
writeIORef s $ u+1
return u
-- Now we'll use the IO-bound supply to create a tree having the desired
-- properties.
{-# NOINLINE getPureSupply #-}
getPureSupply :: IOSupply - IO Supply
getPureSupply s = do
s1 - unsafeInterleaveIO $ getPureSupply s
s2 - unsafeInterleaveIO $ getPureSupply s
n - unsafeInterleaveIO $ getUniqueIO s
return $ Supply n s1 s2
_
Climb to the top of the charts! Play Star Shuffle: the word scramble
challenge with star power.
http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] SYB3 codebase
Hi Greg I forgot to say, that I did not stop using the Shelarcy patch because there was something wrong with the code. On the contrary it served me well for long time. The reason for using the HappS-version was that I wanted something that was Cabalized and that I thought it was good to minimize the number of SYB3's floating around. Greetings, Mads Lindstrøm Haskellians, Does anyone know the status of SYB3 codebase? It appears that FreshLib critically depends on it, but the code downloadable from http://homepages.cwi.nl/~ralf/syb3/code.html dies in make test on the first test with lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$ make test make test1 stem=geq1 ghci -fglasgow-exts -fallow-overlapping-instances -fallow-undecidable-instances -v0 geq1.hs Main.in geq1.out geq1.hs:27:34: Inferred type is less polymorphic than expected Quantified type variable `a1' escapes Probable cause: `geq'' is applied to too few arguments In the first argument of `gzipWithQ', namely `geq'' In the first argument of `and', namely `(gzipWithQ geq' x y)' interactive:1:0: Not in scope: `main' diff -b geq1.out geq1.ref 0a1,4 True False False True make[1]: *** [test1] Error 1 make: *** [test] Error 2 lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$ Is there a newer version of this codebase? Has this functionality been folded into mainline Haskell tree somewhere? Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] SYB3 codebase
Hi Greg To the best of my knowledge it is not maintained anymore :( If you want to use it, you should properly make use of this patch: http://autoforms.svn.sourceforge.net/viewvc/autoforms/trunk/AForms/SYB3_Shelarcy.diff?revision=234view=markuppathrev=400 The patch was made by Kido Takahiro (aka. Shelarcy). The patch makes SYB3 compile with GHC 6.6 and GHC 6.8. However, I do not _think_ anybody else currently uses SYB3 with this patch. As far as I know, I was the only user and I have recently migrated to http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class-0.3 (hereafter know as HappS-SYB3). HappS-SYB3 is based on the SYB3 code you mention, but the code has been changed quite a bit compared to using the Shelarcy patch. So it will properly require some more work. On the other hand, I think the http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class-0.3 version is better maintained, as it is used in HappS project. I have not been able to find any documentation for HappS-SYB3. I _think_ it is because the HappS folks main focus is to use it to support the HappS project. I've have emailed the HappS maintainer about my usage of HappS-SYB3, but I am yet to receive an answer. Thus I have no idea of his position on my usage of HappS-SYB3. If I was you, I would use the Shelarcy patch first, as it will require less work. When everything is working I would migrate to HappS-SYB3, as they have an interest in maintaining their version. Greetings, Mads Lindstrøm P.s. if you decide using the Shelarcy patch then apply it with: patch -u -dSYB3 SYB3_Shelarcy.diff Greg Meredith: Haskellians, Does anyone know the status of SYB3 codebase? It appears that FreshLib critically depends on it, but the code downloadable from http://homepages.cwi.nl/~ralf/syb3/code.html dies in make test on the first test with lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$ make test make test1 stem=geq1 ghci -fglasgow-exts -fallow-overlapping-instances -fallow-undecidable-instances -v0 geq1.hs Main.in geq1.out geq1.hs:27:34: Inferred type is less polymorphic than expected Quantified type variable `a1' escapes Probable cause: `geq'' is applied to too few arguments In the first argument of `gzipWithQ', namely `geq'' In the first argument of `and', namely `(gzipWithQ geq' x y)' interactive:1:0: Not in scope: `main' diff -b geq1.out geq1.ref 0a1,4 True False False True make[1]: *** [test1] Error 1 make: *** [test] Error 2 lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$ Is there a newer version of this codebase? Has this functionality been folded into mainline Haskell tree somewhere? Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Hiding side effects in a data structure
I realise belatedly that my message might have sounded dismissive. My
apologies; it wasn't intended to be. Good ideas are just that: good.
Reinventing them is a sign of good taste.
As to documenting GHC, we try to do that by writing papers. That's easy to
motivate because we get research brownie points for papers. We also put quite
a bit of effort into the Commentary, but it's hard to keep up to date. The
Commentary is a Wiki though, so anyone who discovers some coolness can add a
description to the Wiki. Please do!
Simon
| -Original Message-
| From: Jules Bean [mailto:[EMAIL PROTECTED]
| Sent: 19 October 2007 17:41
| To: Simon Peyton-Jones
| Cc: C Rodrigues; haskell-cafe@haskell.org
| Subject: Re: [Haskell-cafe] Hiding side effects in a data structure
|
| Simon Peyton-Jones wrote:
| Good idea. GHC uses it
| http://darcs.haskell.org/ghc/compiler/basicTypes/UniqSupply.lhs
|
| Lennart Augustsson and friends invented it
| @techreport{Augustsson92a,
|
| ...
|
| You know what would be really nice? A summary of here are all the
| really cool tricks we use in the bowels of GHC and its core libraries.
| Like a GHC code-review for the interested haskell programmer.
|
| Maybe an introductory task for an intern who's working on ghc internals?
| ;)
|
| Jules
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pixel plotter
On Oct 19, 2007, at 15:14 , Andrew Coppin wrote: Peter Verswyvelen wrote: I find it a petty the library does not work with GHCi :-( It has to do with the threaded RTS I guess. Any hints how I could fix this? Yeah, lots of things seem to dislike running in GHCi. (I'm guessing this is to do with trying to talk to C from inside an interpreter... I don't really know for sure why it doesn't work, but it doesn't surprise me.) Could be that (but I think unlikely), or threading (common; gtk2hs has hacks specifically for ghci/runghc), or special initialization needed for windowing programs (I think Windows requires this, and I know OSX does). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] On the verge of ... giving up!
Hello Vimal, Sunday, October 14, 2007, 2:44:05 PM, you wrote: Dear Haskellers, I have been trying my best to read about Haskell from the various first time when i tried to learn haskell i give up and returned only a year later :) about IO: you may try to read http://haskell.org/haskellwiki/IO_inside -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Filesystem questions
Hello Andrew, Friday, October 12, 2007, 9:21:07 PM, you wrote: I notice that getDirectoryContents appears to return its results in alphabetical order. Is this behaviour actually guaranteed? on NTFS filesystem, files are stored in directory alphabetically sorted. on FAT disks the order may be arbitrary -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pixel plotter
Peter Verswyvelen wrote: Yeah I missed that too at first sight... A hint to the author: rename this into README.WIN32.txt or something :-) But I don't think the author of that library reads this mailing list? Mmm... I suppose technically somebody could submit a Darcs patch? ;-) [Darcs even has special support for renaming files...] I find it a petty the library does not work with GHCi :-( It has to do with the threaded RTS I guess. Any hints how I could fix this? Yeah, lots of things seem to dislike running in GHCi. (I'm guessing this is to do with trying to talk to C from inside an interpreter... I don't really know for sure why it doesn't work, but it doesn't surprise me.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
If I understand what you're going for with the code below, then here's
another way to program it in SML that doesn't use exceptions (the
control flow mechanism) at all.
I think what you want is an extensible datatype. Here's the interface I
program to:
signature TAGGED =
sig
(* a tag is the equivalent of a datatype constructor for our extensible
datatype *)
type 'a tag
val newtag : unit - 'a tag
(* the extensible datatype itself:
- the datatype is statically extensible
(you can add new constructors in different parts of the program
text)
- the datatype is dynamically extensible
(you can add new constructors at runtime)
*)
type tagged
(* tag a value
(i.e., the equivalent of a datatype constructor application)
*)
val tag : 'a tag - 'a - tagged
(* match with a given tag
(i.e., the equivalent of pattern matching)
*)
val istagof : 'a tag - tagged - 'a option
end
A simple use is as follows:
structure Use =
struct
open Tagged
val i : int tag = newtag ()
val s : string tag = newtag ()
val l : tagged list = [tag i 1, tag s hi]
fun toString (t : tagged) =
case istagof i t of
SOME (x : int) = Int.toString x
| NONE =
case istagof s t of
SOME (x : string) = x
| NONE = raise Fail don't know about that tag
end
Of course, we could have written this particular code with a datatype.
But you could also add new tags elsewhere in the program, or even
generate them in a loop at runtime.
So for your example below, the point stuff would look like:
type point = int * int
val p : point tag = newtag ()
fun extractPoint (t : tagged) : point =
case istagof p t of
SOME p = p
| NONE = (0,0) (* whatever default value you want *)
And then you'd write
render : tagged - RenderedImage
(Now, you may want render to be an extensible function, so you can add
cases elsewhere in the program, but that's a story for another time.)
Now, the implementation of TAGGED uses the SML exn type, which, despite
the concrete syntax, has absolutely nothing to do with exceptions. It's
much better to think of exn as standing for EXteNsible: it's just an
extensible datatype; the choice of keyword exception for adding a new
datatype constructor is misleading. In fact, TAGGED is just a nicer
interface on top of exn:
structure Tagged : TAGGED =
struct
type 'a tag = ('a - exn) * (exn - 'a option)
type tagged = exn
fun newtag () =
let
exception E of 'a
in
(E, fn (E x) = SOME x
| _ = NONE)
end
fun tag (f, _) x = f x
fun istagof (_, g) x = g x
end
-Dan
On Oct20, TJ wrote:
Dan Licata: Thanks for explaining the mechanics behind it. Knowing how
it (could) be implemented always helps me understand things.
On 10/20/07, Jules Bean [EMAIL PROTECTED] wrote:
Quite often an explicit ADT is much nicer. But they represent two
opposing patterns of code-writing. Explicit ADT allows you to write case
statements handling 'all the logic in one place'; a class forces you to
separate the differences into 'separate instances'.
Nice ADT example. Indeed that would be how I'd do it in SML. Use a
record type holding closures referencing an object of unknown type.
The nice thing I've found about doing it in SML this way is that I can
extract the object back out, using exceptions. e.g.
(* Start Standard ML *)
datatype Renderable = Renderable { render : unit - RenderedImage,
extract : unit - unit, tag : exn }
local
datatype Point = Point Something
exception ExtractMe Point
exception Tag
in
fun mkPoint Something =
let val p = Point Something
in { render = fn () = ... ,
extract = fn () = raise ExtractMe p,
tag = Tag }
end
(* extractPoint would return the Point hidden away in a Renderable. *)
fun extractPoint (Renderable { tag = Tag, extract, ... }) =
(extract (); Point SomethingPointless)
handle ExtractMe p = p
end
(* End SML *)
I don't know if this would work in Haskell, as I'm not familiar with
Haskell exceptions. Anyway I see that Haskell has a Dynamic type...
I've got a good grip on this now, I think. Thanks everyone.
TJ
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
Paul Brown wrote: On 10/17/07, PR Stanley [EMAIL PROTECTED] wrote: Do you trust mathematical materials on Wikipedia? I trust most of them to not be wrong, but I don't trust them to be right. Mathematical concepts are bit like binary search -- getting the flavor right isn't that difficult, but being concise, complete, and correct is very difficult even for experts. In non-mathematics books that I've read (econometrics, operations research, etc.), some of the bits of exposition on fundamentals (multi-var calc, stats/probability, etc.) are not wrong but not quite right. For lay purposes, wikipedia is probably fine, and any resource *that people use* that makes an effort to educate and inform on mathematical concepts deserves some thanks and support. My $0.02. I'd probably agree with most of that. I read a fair bit of stuff on Wikipedia. Some articles are really quite interesting, some are far too vague to comprehend, some are just explained badly, and a fair few are near-empty stubs. It's pot luck. Do I trust the material to be correct? Well, let me put it this way: If I read something from Wikipedia that's wrong, what's the worst that could happen? It's not like I'm going to *use* this information for anything important, so... ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pixel plotter
I find it a petty the library does not work with GHCi :-( It has to do with the threaded RTS I guess. Any hints how I could fix this? Not sure how useful this is, but it works for me. I have a toy project that uses OpenGL and SDL and I have no problems running it from within GHCi in Linux. Perhaps the problem can be narrowed down to Windows. My versions: GHC-6.6.1 SDL-0.4.0 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
Dan Licata: Thanks for explaining the mechanics behind it. Knowing how
it (could) be implemented always helps me understand things.
On 10/20/07, Jules Bean [EMAIL PROTECTED] wrote:
Quite often an explicit ADT is much nicer. But they represent two
opposing patterns of code-writing. Explicit ADT allows you to write case
statements handling 'all the logic in one place'; a class forces you to
separate the differences into 'separate instances'.
Nice ADT example. Indeed that would be how I'd do it in SML. Use a
record type holding closures referencing an object of unknown type.
The nice thing I've found about doing it in SML this way is that I can
extract the object back out, using exceptions. e.g.
(* Start Standard ML *)
datatype Renderable = Renderable { render : unit - RenderedImage,
extract : unit - unit, tag : exn }
local
datatype Point = Point Something
exception ExtractMe Point
exception Tag
in
fun mkPoint Something =
let val p = Point Something
in { render = fn () = ... ,
extract = fn () = raise ExtractMe p,
tag = Tag }
end
(* extractPoint would return the Point hidden away in a Renderable. *)
fun extractPoint (Renderable { tag = Tag, extract, ... }) =
(extract (); Point SomethingPointless)
handle ExtractMe p = p
end
(* End SML *)
I don't know if this would work in Haskell, as I'm not familiar with
Haskell exceptions. Anyway I see that Haskell has a Dynamic type...
I've got a good grip on this now, I think. Thanks everyone.
TJ
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Suspected stupid Haskell Question
On 10/17/07, Thomas Hartman [EMAIL PROTECTED] wrote: Is there a more scientific way of figuring out if one version is better than the other by using, say profiling tools? Profiling Haskell programs is black magic, but of the sort you learn by having a problem to solve. I don't think it requires special genius, just enough motivation. Profiling the interpreter my team created during the ICFP contest did that to me. The GHC heap profiler looked weird to me at first because you are required to convert its output to a PostScript file. However, it's well worth doing. There are several types of profiles, but you would probably be most interested in the biographical profile. The GHC documentation is pretty good and the article Heap Profiling for Space Efficiency[1] may also help. The article was written for the nhc compiler but the tools look the same. Performance profiling is easier - it's just dumped as text output when your program runs. GHC's documentation is really good here. One thing I've learned is to look for two things: 1) Functions that do allocations and execute many times 2) Functions that run lots of times #2 is pretty much universal for profiling, but #1 is unique to Haskell (and probably any pure functional language). Sadly none of these technique work for stack overflows. Or, more likely, I haven't learned how to spot them. Luckily the culprit is usually a fold that isn't strict enough. Albert's post about the Bird book is a good pointer. I just read that chapter myself last night, and he gives a very clear explanation of how lazy evaluation works (he calls it 'outermost reduction') and how strictness interacts with laziness. Hope that helps! Justin [1] http://citeseer.ist.psu.edu/runciman96heap.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why doesn't Hackage link to Haddock documentation anymore?
Will hackage docs use haddock 2.0 any time soon, for libraries that use language extensions not supported by the older haddock? On 10/19/07, Ross Paterson [EMAIL PROTECTED] wrote: On Fri, Oct 19, 2007 at 11:31:06AM +0200, Johan Tibell wrote: Maybe I'm seeing things but from what I remember packages that used to have links to Haddock documentation in their exported modules list no longer has. It's a super useful feature! What happened to those packages? Documentation generation is still haphazard, but I don't think any have been removed. Often newer versions of packages have been added and either the documentation for the new version hasn't been generated yet or the build fails for some reason. Some new versions fail because they depend on packages that will be included with GHC 6.8, but have not yet been released. An example is binary-0.4, though the docs for the earlier versions are still there. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hiding side effects in a data structure
Simon Peyton-Jones wrote:
Good idea. GHC uses it
http://darcs.haskell.org/ghc/compiler/basicTypes/UniqSupply.lhs
Lennart Augustsson and friends invented it
@techreport{Augustsson92a,
...
You know what would be really nice? A summary of here are all the
really cool tricks we use in the bowels of GHC and its core libraries.
Like a GHC code-review for the interested haskell programmer.
Maybe an introductory task for an intern who's working on ghc internals? ;)
Jules
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
On Oct 19, 2007, at 12:11 , Sebastian Sylvan wrote: On 19/10/2007, Kalman Noel [EMAIL PROTECTED] wrote: data ExistsNumber = forall a. Num a = Number a I'm without a Haskell compiler, but shouldn't that be exists a.? The problem is that exists is not valid in either Haskell 98 or any current extension, whereas forall is a very common extension. But you can simulate exists via forall, which is the thrust of these approaches. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
You've almost got it right below. Here's an example of using existentials:
{-# OPTIONS -fglasgow-exts #-}
data AnyNum where
E :: forall a. Num a = a - AnyNum
l :: [AnyNum]
l = [E (1 :: Integer), E (2.0 :: Float)]
neg :: [AnyNum] - [AnyNum]
neg = map (\ (E x) - E (0 - x))
-- testing:
instance Show AnyNum where
show (E x) = show x
main = print (show (neg l))
What's going on here? The idea is that the constructor 'E' of type
AnyNum takes three things
a) a type 'a'
b) a witness that 'a' supports the operations of the Num class
c) a particular value of that type 'a'
So, in a very explicit notation, a value constructed with E might look
like
E Int evidence of Num Int 1
or
E Float evidence of Num Float 2.0
That is, E pairs up a type (with some type class constraints) and a
value of that type. (Of course, in Haskell you only write the value
explicitly.)
The type that you pair up with a value is hidden (existentially
quantified)---it does not show up in the result type of the pair, which
is just AnyNum. So if you just have something of type AnyNum, you don't
know what the type component of the pair is.
Now, when you want to use an AnyNum, you can pattern match against the
pair. In a very explicit notation, you'd write
case x :: AnyNum of
E a evidence of Num a x - body
and in the body, you know that x has type 'a' for some abstract 'a' that
is an instance of Num---but that's all you know! So you can work with x
using the operations of the Num class, but that's it.
Incidentally, why does the Haskell syntax use the keyword forall to
introduce an existential type? The above type
forall a. Num a = a - AnyNum
is just a curried version of the type
(exists a. Num a = a) - AnyNum
The argument to E is morally an existential package (a pair) of a type
and a term (whose type may mention the paired type). Existentials are
the primitive notion here; GHC just happens to provide them using the
data mechanism.
-Dan
On Oct19, TJ wrote:
Henning Thielemann:
class Renderable a where
render :: a - RasterImage
scene :: Renderable a = [a]
This signature is valid, but it means that all list elements must be of
the same Renderable type.
Yes, that's exactly the restriction I'm unhappy about.
You could let the user plug together the alternatives for Renderable. That
is, declare the class Renderable and let the user define and instantiate
data Figure
= Point Something
| Line Something
| Polygon Something
But if I already have the types Point, Line, and Polygon, and I want
to create a union type Figure as above, then my code will look like
this:
data Point = Point Something
data Line = Line Something
data Polygon = Polygon Something
data Figure
= FPoint Point
| FLine Line
| FPolygon Polygon
aFigure = FPoint Point Something
aListOfFigures = [FPoint Point Something, FPolygon Polygon Something,
FLine Line Something]
Is there a way of achieving what I want to do? Existentials maybe? I'm
still learning the basic stuff and don't grok existentials at all, but
I even if I use those, I'll still have to wrap things up in a
constructor, won't I?
I assume, that you could use
http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#universal-quantification
That's a nice page :) From a quick reading, the best I came up with was this:
data R = forall a. Renderable a = V a
instance Show R where
render (R a) = render a
Which is precisely what I meant when I said that I'd still have to
wrap things up in a constructor. Is this hidden type variable thing
what existential types mean?
OT: forall just introduces a new type variable, right?
Thanks,
TJ
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
TJ wrote: Why is it illegal to store values of differing types, but which instance the same class, into a list? e.g. a = [ 1, 2.0 ] :: Num a = [a] The problem is that Num a = [a] really means: forall a. Num a = [a] That is, a list of type Num a = [a] could either be a list of Integers, or a list of Doubles, or ..., but not a heterogeneous list. Slightly varying the type does not help, either: [forall a. Num a = a] This would mean that each and every value in the list is itself polymorphic. What we ultimately need could be written as [exists a. Num a = a] i. e. for each value in the list there is a Num type to which the value belongs. While there is no “exists” quantifier in Haskell types, you can use existentially quantified types (existentials) for your purpose. Given the following data type ExistsNumber data ExistsNumber = forall a. Num a = Number a instance Show Number where -- So we can try this in ghci show (Number a) = show a You may read the data declaration as: “(Number a) has type ExistsNumber if a belongs to the type class Num, i. e. for all a in Num.” Now you can “wrap” any value in the type class Num into an ExistsNumber value, thus “forgetting” its concrete type. You can then construct a list of type [ExistsNumber] easily: [ Number 1, Number (2::Int), Number (3::Double) ] Kalman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Hiding side effects in a data structure
Good idea. GHC uses it
http://darcs.haskell.org/ghc/compiler/basicTypes/UniqSupply.lhs
Lennart Augustsson and friends invented it
@techreport{Augustsson92a,
author = {L Augustsson and M Rittri and D Synek},
title = {Splitting infinite sets of unique names by hidden state changes},
type = {Report 67, Programming Methodology Group, Chalmers University},
month = may,
year = {1992},
keywords = {name supply, monad plumbing, gensym, unique names}
}
Simon
| -Original Message-
| From: [EMAIL PROTECTED] [mailto:haskell-cafe-
| [EMAIL PROTECTED] On Behalf Of C Rodrigues
| Sent: 19 October 2007 15:16
| To: haskell-cafe@haskell.org
| Subject: [Haskell-cafe] Hiding side effects in a data structure
|
|
| While thinking about how to generate unique integer IDs on demand without
| using a state variable, I came up with an interesting design pattern. It's a
| way of doing side-effecting computation outside IO. Referential transparency
| is preserved by making the side effects spatial rather than temporal: by
| hiding side effects behind lazy thunks in a data structure, they can be
| disguised as the output of a single, apparently nondeterministic IO function
| used to data structure. This lets pure code use nondeterministic computation
| without the monadic plumbing required to maintain state.
|
| The getContents function works this way, but I came up with a more
| interesting example. The code below is a source of unique integer IDs that
| is modeled after the RandomGen class. It uses unsafeInterleaveIO under the
| hood, preserving referential transparency but not determinism.
|
| It seems to work. However, I'm not entirely sure how safe my use of
| unsafeInterleaveIO is. In particular, could the two branches of the tree get
| CSE'd? I'm also curious what people think about the general design pattern.
|
| module Unique where
|
| import Control.Monad(liftM)
| import Data.IORef
| import System.IO.Unsafe
|
| -- The goal is to produce an infinite tree of integers where each node in the
| -- tree has a unique value.
| type Unique = Int
| data Supply = Supply Unique Supply Supply
|
| -- The tree can be used in a stateful manner as a source of unique integers.
| getUnique :: Supply - (Unique, Supply)
| getUnique (Supply u s1 _) = (u, s1)
|
| -- The tree can also be split into independent sources of unique integers.
| split :: Supply - (Supply, Supply)
| split (Supply _ s1 s2) = (s1, s2)
|
| -- The catch is, the tree will probably be visited very sparsely, with most
| of
| -- it being skipped. Assigning every node its own integer is very bad,
| because
| -- that will waste most of the 2^32 available integers very quickly. In
| fact,
| -- it can get used up in just 32 calls to getUnique.
| --
| -- Instead, we'll create a tree where integers magically appear only in
| places
| -- where they are actually used.
|
| -- First, we need an IO-bound supply of integers.
| newtype IOSupply = IOSupply (IORef Unique)
|
| newIOSupply :: IO IOSupply
| newIOSupply = liftM IOSupply $ newIORef 0
|
| getUniqueIO :: IOSupply - IO Unique
| getUniqueIO (IOSupply s) = do
| u - readIORef s
| writeIORef s $ u+1
| return u
|
| -- Now we'll use the IO-bound supply to create a tree having the desired
| -- properties.
| {-# NOINLINE getPureSupply #-}
| getPureSupply :: IOSupply - IO Supply
| getPureSupply s = do
| s1 - unsafeInterleaveIO $ getPureSupply s
| s2 - unsafeInterleaveIO $ getPureSupply s
| n - unsafeInterleaveIO $ getUniqueIO s
| return $ Supply n s1 s2
|
| _
| Climb to the top of the charts! Play Star Shuffle: the word scramble
| challenge with star power.
| http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct___
|
| Haskell-Cafe mailing list
| Haskell-Cafe@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
On Fri, 19 Oct 2007, Jules Bean wrote: [EMAIL PROTECTED] wrote: *PLEASE*, show me untrustworthy Wikipedia pages. Any article on a disputed territory or open political dispute. Most articles on a controversial philosophy. Many articles on living people. Articles on controversal topics like HIV/AIDS, climate change, economics, generally things which are called conspiracy theory by enough people. You find many authors which forget good scientific style if the topic is presented in a way which contradicts to their view. Neutral point of view just means Biased view which is shared by enough people. Fortunately, articles on mathematics have several virtues which make them less likely to subject to the problems which plague the above. There is a notion of objective proof, Most proofs in mathematics use intuitive arguments, most proofs are not formalized enough in order to be checked by machines. Ok, this can be considered a deficiency of machine provers. But in the history there were famous proofs which turned out to be wrong. Remember the first proof of the four color theorem of Alfred Kempe (cited from, you guess it, wikipedia :-) http://en.wikipedia.org/wiki/Four_color_theorem ) Or remember the first trial of Andrew Wile to prove the Taniyama-Shimura-Weil conjecture for Fermat's last theorem. It is generally hard to show that a proof is incorrect if the statement is correct. there is a wide peer-reviewed literature which can be used as references, Do referees actually check every proof? there are a disproportionate number of wikipedians with mathematical ability to catch errors. Wikipedia contains the same abuse of notation as all the mathematical literature. I just like to recall the function f(x). Or see the German part of Wikipedia where people have decided to restrict the category Mathematical Function to functions with real and complex parameters and values. (http://de.wikipedia.org/wiki/Kategorie:Mathematische_Funktion) In conclusion I would not trust Wikipedia. But this holds for the rest of the world, too. Scientists must always have a basic stock of scepticism, especially for well known and widely accepted facts/believes. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
[EMAIL PROTECTED] wrote: *PLEASE*, show me untrustworthy Wikipedia pages. Any article on a disputed territory or open political dispute. Most articles on a controversial philosophy. Many articles on living people. I hope I don't have to give examples. Certainly I don't wish to discuss any of the above topics here. Fortunately, articles on mathematics have several virtues which make them less likely to subject to the problems which plague the above. There is a notion of objective proof, there is a wide peer-reviewed literature which can be used as references, there are a disproportionate number of wikipedians with mathematical ability to catch errors. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Type-level arithmetic
Ross Paterson wrote, On Tue, Oct 16, 2007 at 10:56:27AM +1000, Manuel M T Chakravarty wrote: Lennart Augustsson wrote, And Haskell embedded a logical programming language on accident. Well, we are just trying to fix that :) Since types are inferred using unification, and classes are still present, adding functions yields a functional logic programming language at the type level. I used to agree with that, but I changed my opinion. Or more precisely, I'd say that it is a very weak functional logic language. Weak in the sense that it's logic component is essential nil. Let me justify this statement. We have type variables that are like logical variables in logic programming languages. However, we never use function definitions to guess values for type variables. Instead, function evaluation simplify suspends when it depends on an uninstantiated variable and resumes when this variable becomes instantiated. (The functional logic people call this evaluation strategy residuation.) For example, if we have type family T a type instance T Int = Char then, given (T a ~ Char), we do *not* execute T backwards and infer (a = Int). Instead, we leave (T a ~ Char) as it is and evaluate 'T' only when 'a' becomes fixed. There have been proposals for truely functional logic languages using residuation, but they include support for backtracking and producing multiple solutions to a single query. We support neither on the type level. So, the only interaction between type functions and unification left is that function evaluation suspends on uninstantiated type variables and resumes when they become instantiated. This is not functional logic programming, it is *concurrent* functional programming with single-assignment variables. In fact, languages such as Id and pH, which are routinely characterised as concurrent functional, use exactly this model. I don't think the presence of type classes *without* functional dependencies changes this. Manuel PS: You get a *real* functional logic language by truly performing unification modulo an equational theory. This leads to the concept of E-unification and, in our constructor-based context, to narrowing as an evaluation strategy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proposal: register a packageasprovidingseveralAPI versions
Ketil Malde wrote: Claus Reinke [EMAIL PROTECTED] writes: Incedentally, this reminds me that GHC should have a warning for not using explicit import lists (perhaps only for external package imports). for package-level imports/exports, that sounds useful. Isn't there a secret key combination in haskell-mode for Emacs that populates the import lists automatically? No emacs command that I know of, but GHC has the -ddump-minimal-imports flag. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] On the verge of ... giving up!
On 10/19/07, Valery V. Vorotyntsev [EMAIL PROTECTED] wrote: On 10/19/07, Johan Tibell [EMAIL PROTECTED] wrote: If you have a web server somewhere you can use CGIIRC. That's what I did in a similar situation. http://cgiirc.org/ Thanks, Johan! There is one at http://ircatwork.com/ And now I'm in. Thank you very much. :) -- vvv ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] RE: [Haskell] [Fwd: undecidable overlapping instances: a bug?]
Simon Peyton-Jones writes: | I believe that this weak coverage condition (which is also called | the dependency condition somewhere on the wiki) is exactly what GHC | 6.4 used to implement but than in 6.6 this changed. According to | Simon's comments on the trac ticket, this rule requires FDs to be | full to preserve the confluence of the system that is described in | the Understanding Fds via CHRs paper. I have looked at the paper | many times, and I am very unclear on this point, any enlightenment | would be most appreciated. Right. In the language of http://hackage.haskell.org/trac/ghc/ticket/1241, last comment (date 10/17/07), it would be *great* to replace the Coverage Condition (CC) with the Weak Coverage Condition (WCC) as Mark suggests. BUT to retain soundness we can only replace CC with WCC + B WCC alone without (B) threatens soundness. To retain termination as well (surely desirable) we must have WCC + B + C (You'll have to look at the ticket to see what B,C are.) And since A+B+C are somewhat onerous, we probably want to have CC or (WCC + B + C) At least we know of nothing else weaker that will do (apart from CC of course). Like you, Iavor, I find it very hard to internalise just why (B) and (C) are important. But I believe the paper gives examples of why they are, and Martin is getting good at explaining it. Martin: can you give an example, once more, of the importance of (B) (=fullness)? Fullness (B) is a necessary condition to guarantee that the constraint solver (aka CHR solver) derived from the type class program is confluent. Here's an example (taken from the paper). class F a b c | a-b instance F Int Bool Char instance F a b Bool = F [a] [b] Bool The FD is not full because the class parameter c is not involved in the FD. We will show now that the CHR solver is not confluent. Here is the translation to CHRs (see the paper for details) rule F a b1 c, F a b2 d == b1=b2 -- (FD) rule F Int Bool Char== True -- (Inst1) rule F Int a b == a=Bool -- (Imp1) rule F [a] [b] Bool == F a b Bool -- (Inst2) rule F [a] c d == c=[b] -- (Imp2) The above CHRs are not confluent. For example, there are two possible CHR derivations for the initial constraint store F [a] [b] Bool, F [a] b2 d F [a] [b] Bool, F [a] b2 d --_FD (means apply the FD rule) F [a] [b] Bool, F [a] [b] d , b2=[b] -- Inst2 F a b Bool, F [a] [b] d , b_2=[b] (*) Here's the second CHR derivation F [a] [b] Bool, F [a] b2 d --_Inst2 F a b Bool, F [a] b2 d --_Imp2 F a b Bool, F [a] [c] d, b2=[c] (**) (*) and (**) are final stores (ie no further CHR are applicable). Unfortunately, they are not logically equivalent (one store says b2=[b] whereas the other store says b2=[c]). To conclude, fullness is a necessary condition to establish confluence of the CHR solver. Confluence is vital to guarantee completeness of type inference. I don't think that fullness is an onerous condition. Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] On the verge of ... giving up!
On 10/19/07, Valery V. Vorotyntsev [EMAIL PROTECTED] wrote: On 10/18/07, Don Stewart [EMAIL PROTECTED] wrote: Please drop by the irc channel! enthusiasm is always welcome there, and we're pretty much all obsessed too! Maybe that's not The Right Thing(TM) to ask, but anyway. :) My access the world outside the office's LAN is limited to ports 80 and 443. And chat.freenode.net lives on 6667. Once upon a time I could access #haskell via IRC gateway @ irc.e.jabber.ru, but not know, for the reasons unknown. Do you know of any 443:server, forwarding connections to chat.freenode.net:6667? Thanks a lot. If you have a web server somewhere you can use CGIIRC. That's what I did in a similar situation. http://cgiirc.org/ -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] On the verge of ... giving up!
On 10/18/07, Don Stewart [EMAIL PROTECTED] wrote: Please drop by the irc channel! enthusiasm is always welcome there, and we're pretty much all obsessed too! Maybe that's not The Right Thing(TM) to ask, but anyway. :) My access the world outside the office's LAN is limited to ports 80 and 443. And chat.freenode.net lives on 6667. Once upon a time I could access #haskell via IRC gateway @ irc.e.jabber.ru, but not know, for the reasons unknown. Do you know of any 443:server, forwarding connections to chat.freenode.net:6667? Thanks a lot. -- vvv ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Why doesn't Hackage link to Haddock documentation anymore?
Maybe I'm seeing things but from what I remember packages that used to have links to Haddock documentation in their exported modules list no longer has. It's a super useful feature! What happened to those packages? -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Class invariants/laws
Ha, well spotted! GHC's RULE mechanism is specifically designed to allow
library authors to add domain specific optimisations. Just as a library author
can write a buggy implementation of 'reverse', so s/he can write a buggy
optimisation rule.
So I guess it's up to the authors and maintainers of Control.Arrow to decide
whether they want to remove the rule, or simply advertise that instances of
Arrow had better obey it! In which case the libraries list is the place to
discuss.
Simon
| -Original Message-
| From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Ryan
| Ingram
| Sent: 19 October 2007 07:01
| To: Simon Peyton-Jones
| Cc: haskell-cafe@haskell.org
| Subject: Re: [Haskell-cafe] Class invariants/laws
|
| Just today I was looking at the implementation of Arrows and noticed this:
|
| {-# RULES
| compose/arr forall f g .
| arr f arr g = arr (f g)
| ... other rules ...
| #-}
|
| But consider this Arrow:
| newtype (a : b) = LA2 { runLA2 :: [a] - [b] }
|
| instance Arrow (:) where
| arr = LA2 . map
| LA2 ab LA2 bc = LA2 $ \la -
| let dupe [] = []
| dupe (x:xs) = (x : x : dupe xs)
| lb = dupe (ab la)
| in bc lb
| first (LA2 f) = LA2 $ \l - let (as,bs) = unzip l in zip (f as) bs
|
| runLA2 (arr (+1) arr (+1)) [1,2,3]
| = [3,3,4,4,5,5]
|
| runLA2 (arr ((+1) (+1))) [1,2,3]
| = [3,4,5]
|
| Now, the RULE clearly states one of the arrow laws, so it's sound for
| any real Arrow, and : is clearly not a real Arrow. But, :
| satisfies the compiles restriction and breaks the validity of the
| RULE.
|
| -- ryan
|
|
| On 10/18/07, Simon Peyton-Jones [EMAIL PROTECTED] wrote:
| | These invariants are basically impossible to enforce by the compiler,
| | but nonetheless certain classes have laws which are expected to hold,
| | and I would not be surprised if (for example) GHC optimization RULES
| | depended on them.
| |
| | I, in fact, would be surprised if there were such dependencies. (Not
| | that there might not be good reasons to want to rely on such laws for
| | some conceivable optimization, I just doubt that any implementation
| | actually does.)
| |
| | Simon?
|
| I don't believe GHC relies on any class laws. It'd be pretty dangerous to
do so, I think.
|
| Simon
|
| ___
| Haskell-Cafe mailing list
| Haskell-Cafe@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class invariants/laws
Ryan Ingram wrote: On 10/18/07, Janis Voigtlaender [EMAIL PROTECTED] wrote: Yes, but that's a problem of the Arrow library writer, not of GHC. The compiler will never check a RULE. I'm going to disagree a bit here; it's not the problem of the Arrow library writer at all, it's the problem of the implementor of the faulty arrow (me, in this case). Yes, it's an issue between you and the Arrow library writer, not between you and GHC. I think what Simon was asserting is that none of the internal logic of GHC assumes any laws to hold for any type classes. If that's the case, it doesn't address my original point at all, which was talking about the applicability of class laws to optimization RULES. Your original point was that GHC optimization RULES might depend on class laws. That's obviously true, since anyone can write RULES in source code. What I find reasserting about Simon's statement is that no RULES (or other logic) that happen outside the control of the programmer will depend on class laws being true. Note that GHC internally generates RULES for some optimization tasks, without the compiler user having the least inkling. It could easily have been the case that so it also introduces an associativity law for = as given in the H98 report. Only then I would see how code depends on that law actually being true. Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class invariants/laws
Ryan Ingram wrote:
Just today I was looking at the implementation of Arrows and noticed this:
{-# RULES
compose/arr forall f g .
arr f arr g = arr (f g)
... other rules ...
#-}
But consider this Arrow:
newtype (a : b) = LA2 { runLA2 :: [a] - [b] }
instance Arrow (:) where
arr = LA2 . map
LA2 ab LA2 bc = LA2 $ \la -
let dupe [] = []
dupe (x:xs) = (x : x : dupe xs)
lb = dupe (ab la)
in bc lb
first (LA2 f) = LA2 $ \l - let (as,bs) = unzip l in zip (f as) bs
runLA2 (arr (+1) arr (+1)) [1,2,3]
= [3,3,4,4,5,5]
runLA2 (arr ((+1) (+1))) [1,2,3]
= [3,4,5]
Now, the RULE clearly states one of the arrow laws, so it's sound for
any real Arrow, and : is clearly not a real Arrow. But, :
satisfies the compiles restriction and breaks the validity of the
RULE.
Yes, but that's a problem of the Arrow library writer, not of GHC. The
compiler will never check a RULE. So I can, for example, write a rule
that sum xs is zero for any list xs.
I think what Simon was asserting is that none of the internal logic of
GHC assumes any laws to hold for any type classes. If the programmer
tricks the compiler by providing wrong RULES in source files, it's the
programmers problem and fault. It's like using unsafePerformIO.
Ciao, Janis.
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:[EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Fingerprints and hashing
Hello Simon, Thursday, October 11, 2007, 1:42:31 PM, you wrote: For various applications (including identifying common sub-expressions, and version tracking in GHC), I'd like a Haskell library that supports simple fingerprint operations. lots of hash-related links was collected at http://www.encode.ru/forums/index.php?action=vthreadforum=1topic=413 -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
Jules Bean wrote: This looks very very much clearer in GADT syntax, since in GADT syntax you always give constructors explicit types: type ExistsNumber where Number :: forall a . Num a = ExistsNumber a The questions in response to my post have been answered already; I'd like to mention, though, the two typos in your example, which should read instead: data ExistsNumber where Number :: forall a. Num a = a - ExistsNumber Kalman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: Haskell89 grammar extended with links to online report
Hi, I extended the hyperlinked Haskell 98 grammar so that each production now contains also links to all the sections in the online report which explicitly name it. I needed it few times myself so I added it. Some people expressed interest so they may want to check out the update. Javascript must be enabled to have the links functional (both the backward links from a production head to all the usages and also the links to the online report). Here it is: http://www.hck.sk/users/peter/HaskellEx.htm Peter. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
Sebastian Sylvan wrote: On 19/10/2007, Kalman Noel [EMAIL PROTECTED] wrote: data ExistsNumber = forall a. Num a = Number a I'm without a Haskell compiler, but shouldn't that be exists a.? IIRC forall will work too, but the right way to do it is exists, right? No. It's been suggested but that's not how GHC or Hugs existentials work. The syntax isn't actually illogical, it's just very confusing. What (by convention) you are actually doing here is you are annotating the type of the constructor. So you are saying that the constructor 'Number' has the type forall a . Num a = a - ExistsNumber. This is perfectly correct, but it is confusing that what you are doing is annotating the *constructor* and not the data-type itself, per se, although it doesn't much look like it. This looks very very much clearer in GADT syntax, since in GADT syntax you always give constructors explicit types: type ExistsNumber where Number :: forall a . Num a = ExistsNumber a Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
On Fri, 19 Oct 2007, TJ wrote:
Why is it illegal to store values of differing types, but which
instance the same class, into a list? e.g.
a = [ 1, 2.0 ] :: Num a = [a]
After all, sometimes all you need to know about a list is that all the
elements support a common set of operations. If I'm implementing a 3d
renderer for example, I'd like to have
class Renderable a where
render :: a - RasterImage
scene :: Renderable a = [a]
This signature is valid, but it means that all list elements must be of
the same Renderable type.
Instead of hardcoding a bunch of types as being Renderable, as in
data Renderable
= Point Something
| Line Something
| Polygon Something
scene :: [Renderable]
You could let the user plug together the alternatives for Renderable. That
is, declare the class Renderable and let the user define and instantiate
data Figure
= Point Something
| Line Something
| Polygon Something
or
data Shape
= Point Something
| Line Something
| Polygon Something
| Spline Something
or whatever he needs. That's a Haskell 98 solution.
Or maybe
data Point = Point Something
data Line = Line Something
data Polygon = Polygon Something
scene :: { points :: [Point], lines :: [Line], polygons :: [Polygons] }
Is there a way of achieving what I want to do? Existentials maybe? I'm
still learning the basic stuff and don't grok existentials at all, but
I even if I use those, I'll still have to wrap things up in a
constructor, won't I?
I assume, that you could use
http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#universal-quantification
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why doesn't Hackage link to Haddock documentation anymore?
On Fri, Oct 19, 2007 at 11:31:06AM +0200, Johan Tibell wrote: Maybe I'm seeing things but from what I remember packages that used to have links to Haddock documentation in their exported modules list no longer has. It's a super useful feature! What happened to those packages? Documentation generation is still haphazard, but I don't think any have been removed. Often newer versions of packages have been added and either the documentation for the new version hasn't been generated yet or the build fails for some reason. Some new versions fail because they depend on packages that will be included with GHC 6.8, but have not yet been released. An example is binary-0.4, though the docs for the earlier versions are still there. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange subtract operator behavior - and lazy naturals
Hi John, I wrote: - Zero really means 0, not 0 or negative You wrote: Actually, zero does mean zero. There is no such thing as negative numbers in the naturals so it doesn't make sense to say '0 or negative'. Well, then, 0 or error, or 0 or nothing. It clearly does not mean zero. Subtraction is necessarily defined differently of course. As described in the referenced paper, (yes, an enjoyable read, thanks) this is for convenience only. No one is claiming that 1 - 2 == 0 in the naturals. It is just undefined. But we find that returning Zero rather than raising an exception happens to do the right thing for certain common usages of the naturals. Anyway, my point is that you have done two good things here that are orthogonal to each other: a good lazy integral type, and a good naturals type. So why not make the laziness available also for cases where 1 - 2 == 0 does _not_ do the right thing? data LazyInteger = IntZero | IntSum Bool Integer LazyInteger or data LazyInteger = LazyInteger Bool Nat or whatever. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class invariants/laws
[EMAIL PROTECTED] wrote: Yes. But actually what we would need would be that it checks as well that we have implemented at *most* a minimal set of operations. Otherwise, we are back to the point where I can implement both (==) and (/=), and in a way that the supposed invariant is broken. Except that there are many circumstances where I can write an operation that's more efficient (or more lazy, or whatever) than the default, even though they do the same thing. Yes, that's the standard motivation for allowing to implement more of the class methods than would actually be needed. But the (or more lazy, or whatever)-part bodes ill. If I understand correctly what you mean by more lazy, it implies that you are willing to accept variations of complementary methods like (==) and (/=) that do satisfy the expected invariant, except for their behaviour with respect to partially defined inputs. But exactly this up to bottom-reasoning is what gets us into trouble with free theorems in Haskell. If you look at the class-respectance conditions generated for the language subset including selective strictness, you will find preconditions related to _|_. So it is dangerous to do both: 1. record only a subset of those restrictions based on the argument that the methods are anyway tied together via invariants 2. require those same invariants to hold up to _|_ only The result would be free theorems that might be wrong for class instances that satisy the invariants suggested by default method implementations only in this lax way. Better, then, to go the full way and record the restrictions for all class methods, thus being prepared for *any* instance definition, be it fully compliant with the default method implementation, only laxly compliant, or not at all. Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do you trust Wikipedia?
On 10/17/07, PR Stanley [EMAIL PROTECTED] wrote: Do you trust mathematical materials on Wikipedia? I trust most of them to not be wrong, but I don't trust them to be right. Mathematical concepts are bit like binary search -- getting the flavor right isn't that difficult, but being concise, complete, and correct is very difficult even for experts. In non-mathematics books that I've read (econometrics, operations research, etc.), some of the bits of exposition on fundamentals (multi-var calc, stats/probability, etc.) are not wrong but not quite right. For lay purposes, wikipedia is probably fine, and any resource *that people use* that makes an effort to educate and inform on mathematical concepts deserves some thanks and support. My $0.02. -- [EMAIL PROTECTED] http://mult.ifario.us/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Polymorphic (typeclass) values in a list?
On 19/10/2007, Kalman Noel [EMAIL PROTECTED] wrote: data ExistsNumber = forall a. Num a = Number a I'm without a Haskell compiler, but shouldn't that be exists a.? IIRC forall will work too, but the right way to do it is exists, right? So to avoid confusion, use exists rather than forall when you want existential rather than universal quantification. Also, you might want to instantiate the existential type in the class too. E.g. class Render a where render :: a - IO () instance Render ... where -- lots of these data Renderable = exists a . Render a = Renderable a instance Render Renderable where render (Renderable a) = render a Now we can call render on both the actual renderable values themselves, as well as well as the wrapped ones. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class invariants/laws
On 10/18/07, Janis Voigtlaender [EMAIL PROTECTED] wrote:
Yes, but that's a problem of the Arrow library writer, not of GHC. The
compiler will never check a RULE.
I'm going to disagree a bit here; it's not the problem of the Arrow
library writer at all, it's the problem of the implementor of the
faulty arrow (me, in this case). The papers describing arrows clearly
state a set of laws which arrows are expected to follow, and the RULES
specify those laws clearly to anyone looking at the definition of
Arrow.
Also, for arrows in particular, which have hardwired compiler support,
it's more difficult for a user to separate the library from the
compiler; they go hand in hand.
So I can, for example, write a rule that sum xs is zero for any list xs.
Sure, but you're not stating a valid law for lists. Now, if on the
other hand, you had:
-- Invariant: the elements of a ListZero to always sum to 0
newtype Num a = ListZero a = ListZero { unListZero :: [a] }
-- code to implement some useful operations on this type
{-# RULES sum/unListZero forall as. sum (unListZero as) = fromInteger 0 #-}
This rule would be valid according to the documentation specified.
It's not a big step from here to specifying the laws that instances of
a particular class must specify. That's what they're for, after all;
a typeclass is more than just overloading.
I think what Simon was asserting is that none of the internal logic of
GHC assumes any laws to hold for any type classes.
If that's the case, it doesn't address my original point at all, which
was talking about the applicability of class laws to optimization
RULES. Having to restate the arrow laws as optimization rules for
each instance of Arrow would waste a lot of code, as well as requiring
people who implement an Arrow to know not just the Arrow laws but the
internals of GHC's optimization RULES system in order to get the
(often very significant) benefits of the compiler being able to
optimize based on those laws.
-- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic file closing after readFile
I agree with Matthew's comments in the post immediately before this. It takes him two decent paragraphs to explain what is going on, including a description of WHNF, a suggestion to use pen paper, a suggestion to read up on the semantics of unsafeInterleaveIO and more. What I find inconceivable is that people can really believe that these unsafe-lazy functions are a sensible default IO API, given that to use them safely[*] you need to understand all those details. Are we claiming that anyone who doesn't understand the finer points of WHNF, forcing, and GHC's evaluation strategy should not use the haskell IO libraries? [*] Of course, you can use them safely in certain circumstances. But then that doesn't scale. Because your 'first program' works, and then you scale up, and then it breaks, and you find yourself quite unequipped to work out why. Exactly the experience of the original poster in this thread. readFile is actually a worse culprit than hGetContents. If you use hGetContents, at least you have a handle around which you can close explicitly with hClose, which solves the serious OS resource leak (and you can use a bracketing style to do it 'automatically'). Then just remains the asynchronous exception 'hidden bottoms' problem. I suggest the following two versions of readFile as preferable: readFile :: FilePath - IO String readFile f = B.unpack . B.readFile f -- use strict bytestrings to read the file strictly, but into a -- compact memory structure. Then unpack lazily into a conventional -- string but with some luck this intermediate list might fuse away. readFile :: FilePath - (String - IO a) - IO a readFile f act = bracket (openFile f ReadMode) (hClose) (hGetContents h = act) -- this version still uses lazy IO inside, which I don't really like, -- but at least it (a) doesn't open the file unless it actually gets run -- and (b) guarantees to close it again afterwards Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
