Re: [Haskell-cafe] PPM image manipulation
Jared Updike wrote: ... P.S. After googling around for haskell image manipulation (in the hopes of finding some Haskell image lib like VIPS [1] or the Python Imaging Library [2]), I found the assignment spoken of http://cs.anu.edu.au/Student/comp1100/assts/asst1/ just so everyone knows. BTW, does Haskell have an imaging library that people usually turn to? (Or should I add that to my list of cool projects that I need to get around to ...) There are a bunch of libraries listed on the wiki [1], but I don't know if there is one that poeple usually turn to. I rolled my own GD binding [2] when I needed to resize JPEGs, but that's all it does at the moment. Contributions are welcome. /Björn [1] http://www.haskell.org/haskellwiki/Libraries_and_tools/Graphics [2] http://www.cs.chalmers.se/~bringert/darcs/haskell-gd/doc/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
On Mon, 3 Apr 2006, Jared Updike wrote: or ambiguously) with your Sudoku solver? A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles? It's an interesting test to run a Sudoku solver on an empty array. :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code Review: Sudoku solver
Henning Thielemann wrote: On Mon, 3 Apr 2006, Jared Updike wrote: or ambiguously) with your Sudoku solver? A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles? It's an interesting test to run a Sudoku solver on an empty array. :-) I am cleaning up my old (aka inexperienced) solver based on Knuth's dancing links to put on the wiki. The code is very different than most Haskell solutions, since it revolves around a mutable data structure (which is not an MArray). It solves an empty array in 81 steps with no backtracking. It will produce a list of all the solutions of an empty board quite efficiently. Cleaning up my logic based solver will take longer. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
Robert Dockins wrote: On Apr 1, 2006, at 3:23 PM, Brian Hulley wrote: [snip] For particular types T1 and T2, if (f (x::T1))::T2 === g x for all x in T1 then f :: T1-T2 and g ::T1-T2 can be freely substituted since the context T1-T2 cannot tell them apart. Having thought about this a bit more, I realize that this statement is also too strong. In the lambda calculus, extensionality is equivalent to the validity of eta-conversion (Plotkin, Call-by-value, Call-by-name and the lambda calculus, 1975). However, in Haskell, eta-conversion is not valid (ie, meaning-preserving). Observe: f, g :: a - b f = undefined g = \x - undefined x forall x::a, f x === g x === _|_. However, 'seq' can tell them apart. seq f 'a' === _|_ seq g 'a' === 'a' So f and g are not replaceable in all term contexts (in particular, not in 'seq' contexts). I should not have used functions, since in any case for full generality rt is about allowing equivalent expressions to be substituted eg as in: For a particular type T, if f::T === g then f::T and g::T can be freely substituted since the context T cannot tell them apart This of course begs the question of how === is defined and so perhaps is not that useful. If === must be defined extensionally then not all contexts in Haskell are referentially transparent since seq is referentially opaque, but this would render the whole notion of referential transparency useless for Haskell since there would be no way for a user of a library function to know whether or not the argument context(s) are transparent or opaque. At the moment I can't think of a non-extensional definition for === but there must be one around somewhere so that equational reasoning can be used. Regards, Brian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
On Apr 5, 2006, at 10:49 AM, Brian Hulley wrote: Robert Dockins wrote: On Apr 1, 2006, at 3:23 PM, Brian Hulley wrote: [snip] For particular types T1 and T2, if (f (x::T1))::T2 === g x for all x in T1 then f :: T1-T2 and g ::T1-T2 can be freely substituted since the context T1-T2 cannot tell them apart. Having thought about this a bit more, I realize that this statement is also too strong. In the lambda calculus, extensionality is equivalent to the validity of eta-conversion (Plotkin, Call-by-value, Call-by-name and the lambda calculus, 1975). However, in Haskell, eta-conversion is not valid (ie, meaning-preserving). Observe: f, g :: a - b f = undefined g = \x - undefined x forall x::a, f x === g x === _|_. However, 'seq' can tell them apart. seq f 'a' === _|_ seq g 'a' === 'a' So f and g are not replaceable in all term contexts (in particular, not in 'seq' contexts). I should not have used functions, since in any case for full generality rt is about allowing equivalent expressions to be substituted eg as in: For a particular type T, if f::T === g then f::T and g::T can be freely substituted since the context T cannot tell them apart This of course begs the question of how === is defined and so perhaps is not that useful. I had in mind has the same denotational semantics, but the notation is a little sloppy. On the other hand, you could turn the definition around and say that === means two expression which can be freely substituted. To prove properties about ===, you then need to have a very precise definition of the semantics of the programming language. Unfortunately, I don't think Haskell's semantics are developed to quite that point. If === must be defined extensionally then not all contexts in Haskell are referentially transparent since seq is referentially opaque, but this would render the whole notion of referential transparency useless for Haskell since there would be no way for a user of a library function to know whether or not the argument context(s) are transparent or opaque. At the moment I can't think of a non-extensional definition for === but there must be one around somewhere so that equational reasoning can be used. There is a fair bit of disagreement about what referential transparency means. I found the following link after googling around a bit; it seems to address some of these issues. http://www.cs.indiana.edu/~sabry/papers/purelyFunctional.ps Regards, Brian. 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
[Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime error message:
On 2006-04-05 at 12:35EDT Michael Goodrich wrote: Greetings All: GHC gives: Fail: loop Hugs gives: [(ERROR - C stack overflow Nowt's up wi' ' runtime error message. GHC's perfectly lucid. It says your programme went into an infinite loop. This sort of thing belongs on haskell-cafe, by the way. I've moved it there. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
On Apr 5, 2006, at 12:42 PM, Josef Svenningsson wrote: Sorry to barge in in the middle of your discussion here.. Hey, if we wanted a private conversation, we'd take it off-list. :-) On 4/5/06, Robert Dockins [EMAIL PROTECTED] wrote: There is a fair bit of disagreement about what referential transparency means. I found the following link after googling around a bit; it seems to address some of these issues. http://www.cs.indiana.edu/~sabry/papers/purelyFunctional.ps Do you have any reference to the fact that there is any diagreement about the term? I know it has been used sloppily at times but I think it is pretty well defined. See section 4 of the following paper: http://www.dina.kvl.dk/~sestoft/papers/SondergaardSestoft1990.pdf http://en.wikipedia.org/wiki/Referential_transparency http://lambda-the-ultimate.org/node/1237 It may be that experts have a well defined notion of what it means, but I think that non-experts (ie, most people) have a pretty vague idea of exactly what it means. Readers digest: First we need a denotational semantics and a corresponding equality which I call '='. A language is then referentially transparent if for all expressions e,e1 and e2, if e1 = e2 then e[x:=e1] = e[x:=e2]. Here e[x:=e'] denotes substitution where the variable x is replaced with e' in the expression e. So it's a standard substitutivity property. The only problem here is that Haskell has a pretty hairy denotational semantics and I don't think anyone has spelled it out in detail. I think that may be the main problem, at least in this context. We can take a nice lovely definition of rt, as above, but its meaningless without a good semantic model. So we're forced to approximate and hand-wave, which is where the disagreement comes in. The thing which I think comes closest is the following paper which investigates the denotational implications of have seq as a primitive: http://www.crab.rutgers.edu/~pjohann/seqFinal.pdf Cheers, /Josef Thanks for these paper links; I'll be reading them as soon as I find a few moments. 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
[Haskell-cafe] EnumSet with a BSD license
Hi All, Since there is some interest in my EnumSet module, I am reposting it here with a BSD license in anticipation of its rebirth as Data.Set.Enum. Cheers, David EnumSet.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
[Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime error message:
On 2006-04-05 at 14:03EDT Michael Goodrich wrote: BTW, I can't seem to locate 'haskell-cafe'. http://www.haskell.org/mailman/listinfo/haskell-cafe The message responding to my sign-up said nothing about haskell-cafe. Perhaps it should. It's so long since I signed up to haskell that I've forgotten what the sign-up message says. Also, in my infinte-looping application, I am wrapping the calculation in a 'take 1000' function - shouldn't this guarantee termination? Not on its own loop = loop:: Char l = [1,2,3,loop,5,6] putStr $ show $ take 4 l will print 1 2 and 3 and then loop when trying to find the value for the fourth. -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime error message:
Looks like my calulation involves a self referential set of definitions. Is Haskell not able to deal with a self referential set of definitions? I was frankly hoing it would since otherwise there is then the specter of sequence, i.e. that I have to finesse the order in which things are calculated so as to avoid it. Thoughts? cheers, -Mike ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] What's up with this Haskell runtime error message:
On 4/5/06, Michael Goodrich [EMAIL PROTECTED] wrote: Looks like my calulation involves a self referential set of definitions. Is Haskell not able to deal with a self referential set of definitions? Yes, it is, but not if that definition doesn't evaluate to a proper value. For example: main = do print x where x = 3 * x^2 What do you expect this to do? It may help if you toss us the offending code. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
Neil Mitchell wrote: Hi, First, its useful to define referential transparency. In Haskell, if you have a definition f = not Then this means that anywhere you see f, you can replace it with not. For example f True and not True are the same, this is referentially transparent. Now lets define super show which takes a function, and prints its code behind it, so: superShow f = not superShow g = \x - case ... now superShow f /= superShow g, so they are no longer referentially transparent. Hence, you have now broken referential transparency. So you can't show these two functions differently, so what can you do instead? You can just give up and show all functions the same instance Show (a - b) where show x = function This is the constant definition of show mentioned. You can be less restrictive than that. The show function can give different results when applied to functions with different types without breaking anything. -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] show for functional types
Brian Hulley wrote: Greg Buchholz wrote: Hmm. It must be a little more complicated than that, right? Since after all you can print out *some* functions. That's what section 5 of _Fun with Phantom Types_ is about. Here's a slightly different example, using the AbsNum module from... http://www.haskell.org/hawiki/ShortExamples_2fSymbolDifferentiation import AbsNum f x = x + 2 g x = x + 1 + 1 y :: T Double y = Var y main = do print (f y) print (g y) ...which results in... *Main main (Var y)+(Const (2.0)) (Var y)+(Const (1.0))+(Const (1.0)) ...is this competely unrelated? Interesting! Referential transparency (as I understand it) has indeed been violated. Perhaps the interaction of GADTs and type classes was not sufficiently studied before being introduced to the language. So I'm now just as puzzled as you. There's no mystery. The + operator used in that example does not obey '1+1=2'. -- Lennart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's up with this Haskell runtime error message:
Michael Goodrich wrote:
Looks like my calulation involves a self referential set of definitions.
Is Haskell not able to deal with a self referential set of definitions?
I was frankly hoing it would since otherwise there is then the specter
of sequence, i.e. that I have to finesse the order in which things are
calculated so as to avoid it.
Thoughts?
Lazy evaluation is great with self-referential definitions, but id
doesn't do so well with ill-founded definitions. It also won't find
fixpoints of numeric equations. Here are some examples, and then some
explanation.
Things that work:
{- for interactive use in ghci -}
let ones = 1:ones
--infinite list of ones
let counting = 1:map (+1) counting
-- infinite list counting up from one
let fibs = 1:1:zipWith (+) fibs (tail fibs)
--fibbonacci numbers
{- A larger program.
turns references by name into direct references
Try on a cyclic graph, like
buildGraph [(a,[b]),(b,[a])]
-}
import Data.List
import Data.Map as Map
data Node = Node String [Node]
type NodeDesc = (String, [String])
buildNode :: Map String Node - NodeDesc - Node
buildNode env (name,outlinks) =
Node name (concat [Map.lookup other finalBinds | other - outlinks])
buildGraph :: [(String,[String])] - [Node]
buildGraph descs = nodes
where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs
buildExtend binds desc@(name,_) =
let node = buildNode finalBinds desc
in (Map.insert name node binds, node)
Things that will not work:
let x = x
-- no information on how to define x
let x = 2*x + 1
-- this is not treated algebraically
let broke = 1:zipWith (+) broke (tail broke)
-- the second element depends on itself
Recursive definitions in Haskell can be explained by
saying that they find the least-defined fixedpoint of the equations.
Every type in Haskell has all the usual values you would have in a
strict language, plus an undefined value which corresponds to a
nonterminating computation. Also, there are values where subterms
of different types are undefined values of that type rather.
For example, with pairs of numbers there are these posibilites
(x,y)
/ \
(_|_,x) (x,|_|)
\ /
(_|_,_|_)
|
_|_
where x and y represent any defined number, and _|_ is undefined,
or a non-terminating computation. A value on any line is
considered more defined than values on lower lines. Any value which can
be obtained from another by replacing subterms with _|_ is less defined,
if neither can be made from the other that way than neither is more
defined that the other.
Think of a definition like x = f x. That will make x the least-defined
value which is a fixedpoint of f. For example, numeric operations are
(generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and
_|_ is a fixedpoint of \x - 2*x + 1.
for broke, consider the function f = \l - 1:(zipWith (+) l (tail l))
f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_))
= 1:zipWith (+) (1:_|_) _|_
= 1:_|_
so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because
_|_:_|_ is not a fixedpoint, and
f _|_ = 1:something, so _|_ is not a fixedpoint either. If I try that
definition of broke, ghci prints [1 and hangs, indicating that the
rest of the list is undefined.
If multiple definitions are involved, think of a function on a tuple of
all the definitions:
x = y
y = 1:x
corresponds to the least fixedpoint of (\(x,y) - (y,1:x))
The recursiveness in the graph example is more tedious to analyze like
this, but it works out the same way - whatever value of finalBinds is
fed into the recursive equation, you get out a map built by taking the
empty map and adding a binding for each node name. Chase it around a few
more times, and you'll get some detail about the nodes.
Also, posting code really helps if you want specific advice. Thanks to
the hard work of compiler writers, the error message are usually precise
enough for a message like this to describe the possibilites. If you
enjoy my rambling I suppose you should keep posting error messages :)
Brandon
cheers,
-Mike
___
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] Re: [Haskell] What's up with this Haskell runtime error message:
On 4/5/06, ihope [EMAIL PROTECTED] wrote: On 4/5/06, Michael Goodrich [EMAIL PROTECTED] wrote: Looks like my calulation involves a self referential set of definitions.Is Haskell not able to deal with a self referential set of definitions? Yes, it is, but not if that definition doesn't evaluate to a propervalue. For example:main = doprint xwhere x = 3 * x^2What do you expect this to do?It may help if you toss us the offending code. I will be glad to. But just to make it more simple, it is a recursive function with a self referential set of definitionsthat builds a list like this : foo (step,r0,mu0) = bar (step,r1,r0,mu1,mu0) where r1 = r0-step*rd mu1 = mu0-step*mud rd = c*c*mu0 mud = c*c/r0 - (foobar_r z)/c c = baz(z) z = 6.378388e6-r0 baz z | z125 = -0.25*z+1537.5 | otherwise = 0.0169*z+1504.1 foobar_r z | z125 = 0.25 | otherwise = -0.0169 bar (step,r2,r1,mu2,mu1) = (r,z0) : bar (step,r1,r,mu1,m) where r = r2+2*step*rdc m = mu2+2*step*mudc rdc = (rd2+rd1+rd0)/6 mudc = (mud2+mud1+mud0)/6 rd2 = c2*c2*mu2 mud2 = c2*c2/r2 - (foobar_r z2)/c2 rd1 = c1*c1*mu1 mud1 = c1*c1/r1 - (foobar_r z1)/c1 rd0 = c0*c0*m mud0 = c0*c0/r - (foobar_r z0)/c0 c2 = baz(z2) c1 = baz(z1) c0 = baz(z0) z2 = 6.378388e6-r2 z1 = 6.378388e6-r1 z0 = 6.378388e6-r main :: IO () main = do print $ take 100 (foo (0.1, 6.378388e6,0)) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's up with this Haskell runtime error message:
Michael Goodrich wrote: [snip] r = r2+2*step*rdc rdc = (rd2+rd1+rd0)/6 rd0 = c0*c0*m c0 = baz(z0) z0 = 6.378388e6-r The equations above form a loop: each one requires the one below it, and the last one requires the first one. (And yes, baz is strict) Regards, Roberto Zunino. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's up with this Haskell runtime error message:
On 4/5/06, Roberto Zunino [EMAIL PROTECTED] wrote: Michael Goodrich wrote:[snip] r = r2+2*step*rdc rdc = (rd2+rd1+rd0)/6 rd0 = c0*c0*m c0 = baz(z0) z0 = 6.378388e6-rThe equations above form a loop: each one requires the one below it, and the last one requires the first one.(And yes, baz is strict)Regards,Roberto Zunino. Interesting, I was told that it is ok to have a mutually dependent set of definitions - are you saying that Haskell cannot handle this? Also I know what strict means, but why are you saying that baz is strict? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] reading binary files
[questions such as this one should go to cafe] On Wednesday 05 April 2006 20:41, minh thu wrote: 1/ i want to read some binary file (e.g. targa file format : *.tga). -- first way : via IOUArray showInfoHeader1 handle = do a - newArray_ (1,8) :: IO (IOUArray Int Word8) hGetArray handle a 8 idLength - readArray a 1 -- or getElems... putStrLn (id length : ++ show idLength) return () -- second way : via c-like array showInfoHeader2 handle = do b - mallocArray 8 :: IO (Ptr Word8) hGetBuf handle b 8 [idLength] - peekArray 1 b -- or peakArray 8 b The index should be 0 if you want to read the first byte. Also, if you are only interested in the first byte, you could simply idLength - peek b or if it is not the first byte, then idLength - peekByteOff b i However, it is better to use arrays, than pointers. putStrLn (id length : ++ show idLength) free b return () so, briefly, i have to read some content into some kind of buffer (IOUArray Int Word8 or Ptr Word8), then get one (or more) elements from the buffor into a standard haskell variable (is it the correct word ?) (or list). in the second case, i also have to free the buffer. Or use alloca or allocaBytes, which are both a lot faster than malloc and free. in some case, when the data is more than one Word8 long, i have to 'reconstruct' it, i.e.: [x1,x2] - getElems a This will give you a run-time error, because you array is 8 elements long, not 2. You can do x1:x2:_ - ... or better still x1 - readArray b 1 x2 - readArray b 2 Still better: Use one of the available binary serialisation libraries. They are already tuned for efficiency and give you a much nicer high-level API. let x = fromIntegral x1 + fromIntegral x2 * 256 :: Int is it the correct way to read binary files ? Depends on the byte order that is used in your file format. If it is big-endian then correct, else not correct. (I hope I did get this right; I always tend to confuse big- and little-endian.) 2/ haskell is (i heard that once ... :-) a high level language, so it has (must have) good support for abstraction... Sure. See abve mentioned libraries. but in 1/, i have to choose between different kind of array representation (and i dont know which one is better) and it seems to me that the resulting code (compiled) would have to be the same. I strongly recommend using some Array type (IOU or whatever). Ptr is really just a raw pointer into memory: no protection from out-of-bounds access, etc. much like in C. Ptr has been invented for interfacing with C routines, not for regular Haskell programming. HTH, Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's up with this Haskell runtime error message:
Oops, I just realized that you gave me the answer, namely that it won't find fixed points of numeric sets of equations.
Pity, that would really have made Haskell useful for this kind of scientific computing.
On 4/5/06, Brandon Moore [EMAIL PROTECTED] wrote:
Michael Goodrich wrote: Looks like my calulation involves a self referential set of definitions. Is Haskell not able to deal with a self referential set of definitions?I was frankly hoing it would since otherwise there is thenthe specter
of sequence, i.e. that I have to finesse the order in which things are calculated so as to avoid it. Thoughts?Lazy evaluation is great with self-referential definitions, but id
doesn't do so well with ill-founded definitions. It also won't findfixpoints of numeric equations. Here are some examples, and then someexplanation.Things that work:{- for interactive use in ghci -}
let >--infinite list of oneslet counting = 1:map (+1) counting-- infinite list counting up from onelet fibs = 1:1:zipWith (+) fibs (tail fibs)--fibbonacci numbers{- A larger program.
turns references by name into direct referencesTry on a cyclic graph, likebuildGraph [(a,[b]),(b,[a])]-}import Data.Listimport Data.Map
as Mapdata Node = Node String [Node]type NodeDesc = (String, [String])buildNode :: Map String Node - NodeDesc - NodebuildNode env (name,outlinks) = Node name (concat [Map.lookup other finalBinds | other - outlinks])
buildGraph :: [(String,[String])] - [Node]buildGraph descs = nodes where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs buildExtend binds desc@(name,_) = let node = buildNode finalBinds desc
in (Map.insert name node binds, node)Things that will not work:let x = x-- no information on how to define xlet x = 2*x + 1-- this is not treated algebraically
let broke = 1:zipWith (+) broke (tail broke)-- the second element depends on itselfRecursive definitions in Haskell can be explained bysaying that they find the least-defined fixedpoint of the equations.
Every type in Haskell has all the usual values you would have in astrict language, plus an undefined value which corresponds to anonterminating computation. Also, there are values where subtermsof different types are undefined values of that type rather.
For example, with pairs of numbers there are these posibilites (x,y)/ \(_|_,x) (x,|_|)\ / (_|_,_|_) |_|_where x and y represent any defined number, and _|_ is undefined,
or a non-terminating computation. A value on any line isconsidered more defined than values on lower lines. Any value which canbe obtained from another by replacing subterms with _|_ is less defined,if neither can be made from the other that way than neither is more
defined that the other.Think of a definition like x = f x. That will make x the least-definedvalue which is a fixedpoint of f. For example, numeric operations are(generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and
_|_ is a fixedpoint of \x - 2*x + 1.for broke, consider the function f = \l - 1:(zipWith (+) l (tail l))f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_)) = 1:zipWith (+) (1:_|_) _|_
= 1:_|_so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because_|_:_|_ is not a fixedpoint, andf _|_ = 1:something, so _|_ is not a fixedpoint either. If I try thatdefinition of broke, ghci prints [1 and hangs, indicating that the
rest of the list is undefined.If multiple definitions are involved, think of a function on a tuple ofall the definitions:x = yy = 1:xcorresponds to the least fixedpoint of (\(x,y) - (y,1:x))
The recursiveness in the graph example is more tedious to analyze likethis, but it works out the same way - whatever value of finalBinds isfed into the recursive equation, you get out a map built by taking the
empty map and adding a binding for each node name. Chase it around a fewmore times, and you'll get some detail about the nodes.Also, posting code really helps if you want specific advice. Thanks tothe hard work of compiler writers, the error message are usually precise
enough for a message like this to describe the possibilites. If youenjoy my rambling I suppose you should keep posting error messages :)Brandon cheers, -Mike
___ 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] show for functional types
On 4/5/06, Robert Dockins [EMAIL PROTECTED] wrote: Hey, if we wanted a private conversation, we'd take it off-list. :-) :-) Do you have any reference to the fact that there is any diagreement about the term? I know it has been used sloppily at times but I think it is pretty well defined. See section 4 of the following paper: http://www.dina.kvl.dk/~sestoft/papers/SondergaardSestoft1990.pdf http://en.wikipedia.org/wiki/Referential_transparency http://lambda-the-ultimate.org/node/1237 It may be that experts have a well defined notion of what it means, but I think that non-experts (ie, most people) have a pretty vague idea of exactly what it means. The wikipedia article was very enlightening on this subject, especially the disclaimer on the top :-) Thanks! So it's a standard substitutivity property. The only problem here is that Haskell has a pretty hairy denotational semantics and I don't think anyone has spelled it out in detail. I think that may be the main problem, at least in this context. We can take a nice lovely definition of rt, as above, but its meaningless without a good semantic model. So we're forced to approximate and hand-wave, which is where the disagreement comes in. Yes, I know what you mean. In the last few weeks this legacy of hand-waving has been showing its ugly face on the haskell-prime list as well. Maybe its time to sit down and define properly what we mean in certain contexts. It seems we would need more than one semantics to cover the different ways that reason about Haskell program. Just so that one can say: Here I'll be using Fast'n-Loose Reasoning(TM) or This law holds in the Handwaving Semantics(TM). The point is to be able to reference these precisely defined approximations and thus enjoying being both sloppy and precise at the same time. But it's real work doing this kind of thing. During a graduate course at Chalmers we started at something like this but it grew pretty hairy pretty quickly. Cheers, /Josef ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What's up with this Haskell runtime error message:
On Wednesday 05 April 2006 04:51 pm, Michael Goodrich wrote:
Oops, I just realized that you gave me the answer, namely that it won't
find fixed points of numeric sets of equations.
Pity, that would really have made Haskell useful for this kind of
scientific computing.
See section 4 of:
http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html
See also:
http://www.haskell.org/haskellwiki/Libraries_and_tools/Mathematics
http://users.info.unicaen.fr/~karczma/arpap/
On 4/5/06, Brandon Moore [EMAIL PROTECTED] wrote:
Michael Goodrich wrote:
Looks like my calulation involves a self referential set of
definitions.
Is Haskell not able to deal with a self referential set of definitions?
I was frankly hoing it would since otherwise there is then the
specter of sequence, i.e. that I have to finesse the order in which
things are calculated so as to avoid it.
Thoughts?
Lazy evaluation is great with self-referential definitions, but id
doesn't do so well with ill-founded definitions. It also won't find
fixpoints of numeric equations. Here are some examples, and then some
explanation.
Things that work:
{- for interactive use in ghci -}
let ones = 1:ones
--infinite list of ones
let counting = 1:map (+1) counting
-- infinite list counting up from one
let fibs = 1:1:zipWith (+) fibs (tail fibs)
--fibbonacci numbers
{- A larger program.
turns references by name into direct references
Try on a cyclic graph, like
buildGraph [(a,[b]),(b,[a])]
-}
import Data.List
import Data.Map as Map
data Node = Node String [Node]
type NodeDesc = (String, [String])
buildNode :: Map String Node - NodeDesc - Node
buildNode env (name,outlinks) =
Node name (concat [Map.lookup other finalBinds | other - outlinks])
buildGraph :: [(String,[String])] - [Node]
buildGraph descs = nodes
where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs
buildExtend binds desc@(name,_) =
let node = buildNode finalBinds desc
in (Map.insert name node binds, node)
Things that will not work:
let x = x
-- no information on how to define x
let x = 2*x + 1
-- this is not treated algebraically
let broke = 1:zipWith (+) broke (tail broke)
-- the second element depends on itself
Recursive definitions in Haskell can be explained by
saying that they find the least-defined fixedpoint of the equations.
Every type in Haskell has all the usual values you would have in a
strict language, plus an undefined value which corresponds to a
nonterminating computation. Also, there are values where subterms
of different types are undefined values of that type rather.
For example, with pairs of numbers there are these posibilites
(x,y)
/ \
(_|_,x) (x,|_|)
\ /
(_|_,_|_)
_|_
where x and y represent any defined number, and _|_ is undefined,
or a non-terminating computation. A value on any line is
considered more defined than values on lower lines. Any value which can
be obtained from another by replacing subterms with _|_ is less defined,
if neither can be made from the other that way than neither is more
defined that the other.
Think of a definition like x = f x. That will make x the least-defined
value which is a fixedpoint of f. For example, numeric operations are
(generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and
_|_ is a fixedpoint of \x - 2*x + 1.
for broke, consider the function f = \l - 1:(zipWith (+) l (tail l))
f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_))
= 1:zipWith (+) (1:_|_) _|_
= 1:_|_
so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because
_|_:_|_ is not a fixedpoint, and
f _|_ = 1:something, so _|_ is not a fixedpoint either. If I try that
definition of broke, ghci prints [1 and hangs, indicating that the
rest of the list is undefined.
If multiple definitions are involved, think of a function on a tuple of
all the definitions:
x = y
y = 1:x
corresponds to the least fixedpoint of (\(x,y) - (y,1:x))
The recursiveness in the graph example is more tedious to analyze like
this, but it works out the same way - whatever value of finalBinds is
fed into the recursive equation, you get out a map built by taking the
empty map and adding a binding for each node name. Chase it around a few
more times, and you'll get some detail about the nodes.
Also, posting code really helps if you want specific advice. Thanks to
the hard work of compiler writers, the error message are usually precise
enough for a message like this to describe the possibilites. If you
enjoy my rambling I suppose you should keep posting error messages :)
Brandon
cheers,
-Mike
---
-
___
