[GHC] #1236: System.Mem.Weak breaks referential transparency
#1236: System.Mem.Weak breaks referential transparency -+-- Reporter: [EMAIL PROTECTED] | Owner: Type: bug | Status: new Priority: normal| Milestone: Component: libraries/base| Version: 6.6 Severity: normal|Keywords: Difficulty: Unknown |Testcase: Architecture: Unknown | Os: Unknown -+-- Consider the following two functions: foo = do mkWeakPtr y (Just launchMissiles) return y where y = 42 bar = do mkWeakPtr 42 (Just launchMissiles) return 42 These two functions are equivalent right? After all referential transparency means that if y = 42, then anywhere y occurrs I can write 42. The problem is that if I call foo, and hang on to the return value, then launchMissiles won't be called until some time after I stop using the return value, but if I call bar, then launchMissiles may be called any time, including before bar returns! Looks to me like finalizers break referential transparency, so System.Mem.Weak is broken, though I'm quite willing to be proven wrong. cheers, Tom -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1236 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List
That would actually be wrong. It's easy to come up with examples
where this identity is false.
For instance:
data T = T Int Int deriving (Ord, Show)
instance Eq T where
T x _ == T y _ = x == y
ts = [T 1 1, T 1 undefined]
On Mar 18, 2007, at 23:51 , GHC wrote:
#1218: Add sortNub and sortNubBy to Data.List
+---
Reporter: neil| Owner:
Type: proposal| Status: new
Priority: normal | Milestone: Not GHC
Component: libraries/base |Version:
Severity: normal | Resolution:
Keywords: | Difficulty: Unknown
Testcase: | Architecture: Unknown
Os: Unknown |
+---
Comment (by dons):
How about rather than changing the api, purely for efficiency
reasons, we
just add a rewrite rule to Data.List for this optimisation?
The rule would be:
{{{
{-# RULES
sort/nub sort . nub = map head . group . sort
#-}
}}}
sort . nub will be rewritten to the optimised case, and we won't
need to
further complicate the API.
Quite often now it is possible for the library author to expose
only a
small, generic API, while providing internal rules for specific
optimised
cases. This keeps the interface small, while still providing
performance.
Data.ByteString does this in a number of places, for example:
{{{
{-# RULES
FPS specialise filter (== x) forall x.
filter (== x) = filterByte x
#-}
}}}
I'd really not like to see more functions exposed in the list
interface,
only as optimisations, that could be better provided via RULES.
--
Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1218
GHC http://www.haskell.org/ghc/
The Glasgow Haskell
Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[Haskell] Quicksearch vs. lazyness
Hello, say, we want to find the k'th element in a sorted list. In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array. In Haskell one could implement this idea as follows: qsearch k [] = error ... qsearch k (x:xs) | lsmaller = k = qsearch k smaller | lsmaller == 0 k 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (= x) xs lsmaller = length smaller greater = filter ( x) xs However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? Best regards, Steffen ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Quicksearch vs. lazyness
I left my copy of Chris Okasaki's Functional Data Structures at home, but I seem to recall (vaguely) that his heap sort algorithm was best for sorting/searching the first k elements of an orderable sequence. If you don't have a copy of this book, you should definitely get one. It is his dissertation, cleaned up and supplemented (on the website) with Haskell code (the basis of the Edison library), that examines in detail the role of laziness in data structures and algorithms on them. His notions of Banker's credits and Physicist's credits is an easily-teachable notion of evaluating computational complexity. Dan Steffen Mazanek wrote: Hello, say, we want to find the k'th element in a sorted list. In imperative languages it is much more efficient to not use quicksort first and get the k'th element later, but to use a quicksearch algorithm that sorts only the relevant parts of the array. In Haskell one could implement this idea as follows: qsearch k [] = error ... qsearch k (x:xs) | lsmaller = k = qsearch k smaller | lsmaller == 0 k 1 = qsearch (k-1) greater | lsmaller == 0 = x | otherwise = qsearch (k-lsmaller) (x:greater) where smaller = filter (= x) xs lsmaller = length smaller greater = filter ( x) xs However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? Best regards, Steffen ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] Haskell Chess
Andrzej, I'd love to hear some of your thoughts on these things. I agree with you about brute-force not being the best approach in haskell (or maybe at all). I think we should switch to haskell-cafe, since that's where much of this discussion has gone, and that's more for extended discussions anyway. On 3/18/07, Andrzej Jaworski [EMAIL PROTECTED] wrote: Didactic it may be but brute force on search trees means in Haskell problem with garbage collection. So students may build a punch but loose a street fight. Instead of using Haskell as a hammer I would rather explore what monadic programming can offer in terms of encapsulating constraints, heuristics, modal logic or agents. Chess is a human game so why not use computing along this line and employ Haskell on humane terms? The force is with us! Cheers, -Andrzej ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: Quicksearch vs. lazyness
Steffen Mazanek wrote: say, we want to find the k'th element in a sorted list. I assume that you want to find the k'th smallest element of an unsorted list by sorting it? [...] However, I was wondering whether it might be possible to implement quicksort in a way that quicksearch is done out of the box by lazy evaluation. Is there any way to do this? Yes, that can be done. It's a small extension of the folklore (?) example minimum = head . mergesort that extracts the smallest element of a list. Given a proper mergesort, laziness will ensure that this function actually runs in O(n) time instead of the expected O(n log n). Apparently, the first k smallest elements now can be obtained by take k . mergesort which may run in O(n + k*log n) time with a laziness-friendly mergesort. From my understanding for small k's lazy evaluation already does the trick for the naive quicksort algorithm (quicksort smaller ++ [x] ++ quicksort greater), doesn't it? Is there a search algorithm that makes better use of lazy evaluation out of the box? No, as far as I thought about quicksort, it needs O(n log n) to produce the first element. But even the mergesort implementation has to be chosen carefully as I've seen many that still need O(n log n) just to return the smallest element. Alas, her is a laziness-friendly mergesort: mergesort [] = [] mergesort xs = foldtree1 merge $ map return xs foldtree1 f [x] = x foldtree1 f xs = foldtree1 f $ pairs xs where pairs []= [] pairs [x] = [x] pairs (x:x':xs) = f x x' : pairs xs merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = if x = y then x:merge xs (y:ys) else y:merge (x:xs) ys Why does this work? The function 'foldtree1' folds the elements of a list as if they where in a binary tree: foldrtree1 f [1,2,3,4,5,6,7,8] == ((1 `f` 2) `f` (3 `f` 4)) `f` ((5 `f` 6) `f` (7 `f` 8)) The important point is that this expression is constructed in O(n + n/2 + n/4 + n/8 + ..) = O(n) time. Now, given such a binary tree of `merge` operations, getting the next list element of the result takes O(log n) time. Why? Because the merge in the middle gets the next element either from its left or its right subexpression which in turn gets its element from its left or its right subexpression and so on. Clearly, we only need logarithmically many steps to hit the bottom. Putting both together, we see that we have to pay O(n + k*log n) steps to build the expression and to fetch the first k elements. Making this argument rigorous with a suitable debit invariant is left to the attentive reader :) Regards, apfelmus ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Summer of Code project proposal
Hello All, I am Nikhil N, a third year Computer Science student from India. I am looking at building a good IDE for people learning Haskell(as part of SoC).This IDE will be modeled on Dr Scheme or blueJ. I love coding in C and Haskell.I believe that the Haskell IDE will enhance the understandability and popularity of the language. I am looking for someone who could mentor me and guide me through the project. I am confident of completing the project successfully and am excited at contributing to the community. Regards Nikhil N ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: strict bits of datatypes
Simon Peyton-Jones wrote: | strict fields have no effect on deconstructing data types. That's GHC's behaviour too. I think it's the right one too! (It's certainly easy to explain.) This reminds me of something I discovered about using strict fields in AVL trees (with ghc). Using strict fields results in slower code than doing the `seq` desugaring by hand. If I have.. data AVL e = E | N !(AVL e) e !(AVL e) .. etc then presumably this.. case avl of N l e r - N (f l) e r desugars to something like .. case avl of N l e r - let l' = f l in l' `seq` r `seq` N l' e r but IMO it should desugar to.. case avl of N l e r - let l' = f l in l' `seq` N l' e r which is what I ended up writing by hand all over the place (dropping the strictness annotation in the data type). That is, variables that have been obtained by matching strict fields (r in the case) should not be re-seqed if they are re-used in another strict context. Now this explanation for the slow down I observed is just speculation on my part (I don't actually know what ghc or any other compiler does). But on modern memory architectures, forcing the code to inspect heap records that it shouldn't have to inspect will be a bad thing. So semantically I agree with strict fields have no effect on deconstructing data types, but they should have an effect on the code that an optimising compiler generates IMO. Regards -- Adrian Hey ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
RE: strict bits of datatypes
| This reminds me of something I discovered about using strict fields in | AVL trees (with ghc). Using strict fields results in slower code than | doing the `seq` desugaring by hand. That is bad. Can you send a test case that demonstrates this behaviour? | If I have.. | | data AVL e = E | | N !(AVL e) e !(AVL e) | .. etc | | then presumably this.. | | case avl of N l e r - N (f l) e r | | desugars to something like .. | | case avl of N l e r - let l' = f l | in l' `seq` r `seq` N l' e r | | but IMO it should desugar to.. | | case avl of N l e r - let l' = f l | in l' `seq` N l' e r I agree. If it doesn't please let me know! Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
type aliases and Id
Hi all,
Suppose I have a datatype:
data Foo a = Foo {
int :: a Int,
char :: a Char
}
where I start off with (Foo Nothing Nothing) :: Foo Maybe, gradually
accumulate values until I have (Foo (Just 5) (Just 'c')), and then I
want to remove the Maybe type so I can lose all the now-redundant Just
constructors.
Well, suppose in actual fact I prefer the name CanBe to Maybe.
Then for the first part I want
type CanBe a = Maybe a
foo :: Foo CanBe
foo = ...
but of course this fails because CanBe is a non-fully-applied type
synonym in foo :: Foo CanBe, and I can fix this by eta-reducing thus:
type CanBe = Maybe
foo :: Foo CanBe
foo = ...
Now for the second part I want
type Id a = a
foo' :: Foo Id
foo' = ...
but again Id is not fully applied. However, this time I cannot
eta-reduce it! type Id = is a parse error, as is type Id.
I'd really like to be able to define an eta-reduced Id; I see two
possibilities:
* Allow type Id = (I prefer this to type Id as I think we are more
likely to want to use the latter syntax for something else later on).
* Implementations should eta-reduce all type synonyms as much as
possible, e.g.
type T a b c d = X a b Int c d
is equivalent to
type T a b = X a b Int
and
type Id a = a
is equivalent to a type that cannot be expressed directly.
Any opinions?
Thanks
Ian
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
Re: type aliases and Id
Ian, Mmm... * Allow type Id = (I prefer this to type Id as I think we are more likely to want to use the latter syntax for something else later on). Looks kind of funny; I'm not too thrilled. * Implementations should eta-reduce all type synonyms as much as possible, e.g. type T a b c d = X a b Int c d is equivalent to type T a b = X a b Int and type Id a = a is equivalent to a type that cannot be expressed directly. I like this alternatie a bit better, but I can also see how it introduces a lot of potential confusing, especially for novice Haskell programmers. You write something and the compiler goes along with something else... Maybe this will serve as a source of inspiration: http:// portal.acm.org/citation.cfm?doid=581478.581496 [1]. Cheers, Stefan [1] Matthias Neubauer and Peter Thiemann. Type classes with more higher-order poly- morphism. In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP ’02), Pittsburgh, Pennsylvania, USA, October 4–-6, 2002, pages 179–-190. ACM Press, 2002. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: type aliases and Id
On 3/19/07, Ian Lynagh [EMAIL PROTECTED] wrote: I'd really like to be able to define an eta-reduced Id; I see two possibilities: * Allow type Id = (I prefer this to type Id as I think we are more likely to want to use the latter syntax for something else later on). * Implementations should eta-reduce all type synonyms as much as possible, e.g. type T a b c d = X a b Int c d is equivalent to type T a b = X a b Int and type Id a = a is equivalent to a type that cannot be expressed directly. Any opinions? A third possibility is to have Id be a special primitive type constructor of kind * - * that implementations handle internally. If you wanted to give it different name you could use an eta-reduced type synonym for that, of course. That's the approach I took when I needed an identity type function in the Bluespec compiler, and that worked out reasonably well. Part of the reason that worked out, though, is that we already had a normalization point during typechecking where certain special type constructors (related to numeric types) were cleaned out, so adding Id just extended that a little. I don't know whether adding such a constructor would be an equally simple change for Haskell implementations. And there's the separate argument that requiring eta-reduction of all type synonyms might be an interesting new feature in its own right (since I think you can say other new things beyond type Id a = a). - Ravi ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
Re: type aliases and Id
Hello, On 3/19/07, Lennart Augustsson [EMAIL PROTECTED] wrote: Ravi, Ganesh and I were discussing today what would happen if one adds Id as a primitive type constructor. How much did you have to change the type checker? Presumably if you need to unify 'm a' with 'a' you now have to set m=Id. Do you know if you can run into higher order unification problems? My gut feeling is that with just Id, you probably don't, but I would not bet on it. It seems to me that even with just ''Id'' the problem is tricky. Suppose, for example, that we need to solve ''f x = g y''. In the present system we can reduce this to ''f = g'' and ''x = y'''. However, if we had ''Id'', then we would have to delay this equation until we know more about the variables that are involved (e.g., the correct solution might be ''f = Id'' and ''x = g y''). -Iavor ___ Haskell-prime mailing list Haskell-prime@haskell.org http://www.haskell.org/mailman/listinfo/haskell-prime
[Haskell-cafe] Re: System.Random StdGen read fails on some strings? [also continues: Random/StdGen/read: there is something unclear (or misunderstood!)]
On Tue, 13 Mar 2007 14:44:46 +0100, Zara [EMAIL PROTECTED]
wrote:
On Tue, 13 Mar 2007 00:37:46 -0700, Fritz Ruehr
[EMAIL PROTECTED] wrote:
According to the documentation for System.Random (see http://
haskell.org/ghc/docs/latest/html/libraries/base/System-Random.html):
In addition, read may be used to map an arbitrary string (not
necessarily one produced by show) onto a value of type StdGen. In
general, the read instance of StdGen has the following properties:
* It guarantees to succeed on any string.
* ...
On the other hand, I get the following on the (admittedly stupid,
spur-of-the-moment) String argument whateva:
Hugs :l System.Random
System.Random read whateva :: StdGen
Program error: Prelude.read: no parse
..
There seems to be a limit on 6 characters. Any string under 6
characters works nice, any over that limit will fail.
test program:
\begin{code}
module Test where
import Random
rd :: String - StdGen
rd = read
testit :: String - [Int]
testit [] = []
testit xt@(_:xs) = (testit xs) ++ [fst (randomR (1::Int,50) (rd xt))]
\end{code}
testit thing wotks nice,
testit morethanthing stops after the sixth number in the list.
Both in HUGS and GHC, last versions
The problem seems to lie in base/System/Random.hs:
\begin{code}
{-
If we cannot unravel the StdGen from a string, create
one based on the string given.
-}
stdFromString :: String - (StdGen, String)
stdFromString s= (mkStdGen num, rest)
where (cs, rest) = splitAt 6 s
num= foldl (\a x - x + 3 * a) 1 (map ord cs)
\end{code}
If we change the number on splitAt, the string limit to give an error
changes.
I think that when we feed an arbitrary string to readsPrec of
Random.StdGen, we should return nothing, that is, we should consume
the whole string. So, I propose th change that function to be:
\begin{code}
{-
If we cannot unravel the StdGen from a string, create
one based on the string given. We consume it all.
-}
stdFromString :: String - (StdGen, String)
stdFromString s= (mkStdGenBis num, )
where num= foldl (\a x - x + 3 * a) 1 (map ord s)
\end{code}
This solution solves *our* problem, but I would like to receive
comments to it. Where may I find someone responsible for this library,
to see if the change is adequate, or why not?
Best regards,
Zara
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Visibility of definitions in Hugs Prelude
I am wondering about the visibility of definitions in the Hugs Prelude. More specifically, when I ask for info about the Eq class, I see a lot of instances, including: instance Eq Key On the other hand, Key is not in scope: Hugs :info Key Unknown reference `Key' I imagine this has to do with importing/exporting, or maybe some modern Hugs empty-Prelude funkiness. Or perhaps it is because Key is a non-standard export (but that is just a comment in the Prelude). In any case, is it intended that :info will tell me about things that I (and it) can't otherwise see? Please forgive my naivete re module rules in advance ... . -- Fritz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Algorithms
A. understand the problem B. decompose or reduce it into subproblems C. solve the subproblems D. compose a solution from the sub-solutions -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ --- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance Help
On Friday 16 March 2007 21:29, David Brown wrote:
Ian Lynagh wrote:
On Sun, Mar 11, 2007 at 08:18:44PM +, Dominic Steinitz wrote:
I have re-written the sha1 code so that it is (hopefully) easy to see
that it
faithfully implements the algorithm (see
http://www.itl.nist.gov/fipspubs/fip180-1.htm). Having got rid of the
space
leak, I have been trying to improve performance.
Currently, the haskell code is 2 orders of magnitude slower than the
sha1sum
that ships with my linux.
I don't know if this is useful to you, but darcs has some SHA1 code that
IIRC is much closer to C's performance. It currently uses darcs' own
FastPackedString library, but porting it to ByteString should be fairly
easy.
See SHA1.lhs in http://www.abridgegame.org/repos/darcs-unstable
It might even be able to be made faster still by calling lower-level
functions than {shift,rotate}{L,R} directly.
I ended up deciding to call SHA1 routines out of openssl. For
applications where this is possible, it does very well, I got about
2.5 times the speed out of it, compared to ordinary C implementations.
But, since harchive spends most of its CPU computing SHA1 hashes (and
almost all of the rest in zlib), it is worth a complex binding there.
Dave
Ian, Dave,
Thanks. My goal is to have natural haskell code that's reasonably efficient. I
don't have a problem to solve that needs an efficient implementation of SHA1.
I'm going to try apfelmus' suggestions next and then (if I ever get yhc to
build) start looking at what gets generated.
Dominic.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Re: HS-Plugins 1.0 chokes on simple test, WinXP GHC-6.6 (Conal Elliott)
[mailto:[EMAIL PROTECTED] On Behalf Of Vivian McPhail I just setup and installed hs-plugins from darcs on WinXP using ghc-6.6 and MSYS. The hs-plugin test suite all passes. Can you send me something that generates your error and I'll have a look at it. Vivian Well, if I haven't misunderstood what you're asking for, there is the original test case at the root of this mail thread (copied below). This produces the same error message that Conal gets: Main: c:/ghc/ghc-6.6/HSbase.o: unknown symbol `_free' Main: user error (Dynamic loader returned: user error (resolvedObjs failed.)) Alistair --- module Test1 where test1 = putStrLn test1 module Main where import Prelude hiding (catch) import Control.Exception import Data.List import System.Environment import System.Plugins instance Show (LoadStatus a) where show (LoadFailure errors) = LoadFailure - ++ (concat (intersperse \n errors)) show (LoadSuccess m p) = LoadSuccess main = do a - getArgs let modName = case a of (n:_) - n _ - Test1 let modPath = ./ ++ modName ++ .o let method = test1 fc - catch (load modPath [] [] method) (\e - return (LoadFailure [Dynamic loader returned: ++ show e])) case fc of LoadFailure errors - do fail (concat (intersperse \n errors)) LoadSuccess modul proc - do let p :: IO (); p = proc proc * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: System.Random StdGen read fails on some strings? [also continues: Random/StdGen/read: there is something unclear (or misunderstood!)]
Zara Good point. It's a bit stupid that 'read' fails utterly on strings shorter than 6. I don't thin StdRandom has an owner at the moment. There's a process for proposing library changes, described under guidelines for developers here http://haskell.org/haskellwiki/Libraries_and_tools That's the way to get your change adopted. However, in this case the bug is in your code. The function 'read' (which you use) fails unless it consumes its entire input. That is not what you want here. The right thing to do is to use 'reads' instead. The wrong thing to do is to make reading a StdGen read the entire input string! Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Haskell Chess
Hello again, first of all, thank you Don for your help in making hsChess accessible. I have to have a look at darcs and cabal first :-) I have added some more content and a discussion page to the wiki, please contribute your thoughts. Furthermore I added a link to the german project and task description used in the exercises; the English version will be the wiki (although it has no convert2tex function). Best regards, Steffen Donald Bruce Stewart schrieb: smazanek: Hello again, I got a lot of interesting and useful comments on my posting about Haskell Chess. Somebody suggested using the program for benchmarks. Several people asked me to open the program for contributions. And others were just interested in the exercises. It is probably the best to branch the development, so that we have a teachers' and a hackers' version (ease of understanding and learning paradigms vs. efficiency and implementation of full ruleset). I will do the necessary steps next week (svn, etc). Somebody already offered help for cabalizing hsChess. hsChess has been cabalised, and is available now via darcs; darcs get http://www.cse.unsw.edu.au/~dons/code/contrib/hsChess/ You can also browse the source directly: http://www.cse.unsw.edu.au/~dons/code/contrib/hsChess/ Several people asked me for the exercises so I started the wiki page http://haskell.org/haskellwiki/Learning_Haskell_With_Chess on this topic. I will add more content when I am back to office. Every contribution and discussion is welcome. I am happy to host the code at the above url, unless Steffen, you have a better place to host the repository? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Performance Help
Thanks. Fusing the ws is trickier. Directly appealing to the fibonacci-number example is not recommended because this would mean to keep the last 16 ws in memory and shifting them right to left by hand. But as the Are you saying this because we don't want a 16-tuple? Alternate method of computation on the website suggests, you can delegate the shifting to an index that shifts around mod 16. Having a mutable array is helpful, then. Are you saying that because haskell doesn't really have mutable arrays, this is ruled out? Of course, you can also fill a large static (boxed!) array of 80 Word8s via ws :: Data.Array.IArray.Array Int Word8 ws = accumArray 0 (0,80) (curry snd) $ zip [0..15] xs ++ [(i, xxor i) | i-[16..80]] where xxor i = ws ! (i-16) `xor` ws ! (i-3) `xor` ws ! (i-8) `xor` ws ! (i-14) or something like that (I didn't care about correct indices and bounds). GHC can fuse such array accumulations. Why is an array better than a list? Is it because (!) is O(1) and (!!) is O(n)? In general, keeping stuff in lists is not wrong, but ByteStrings are more adapted to current CPU and RAM architecture. I'm not clear how ByteStrings help here. We need to put bits into 32 words and operate on these. Dominic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
Thanks for the long answer David, David House wrote: On 17/03/07, Fawzi Mohamed [EMAIL PROTECTED] wrote: [...] Surely within a group of related types there'd be no overlapping names anyway? yes, but I found out that I would have an overlap with functions that I wanted to use and function I wanted to define, resulting in quite some qualifying. Also arrays, inset,... have quite some overlapping. For array the use of the IArray typeclass kept the things nice also using Arrays and UArrays together, but adding IntSet to the whole worked only qualifying, and then I also wanted to define a fold for my type... I found Data.Foldable, but then in the end I just prefixed my operation names which is what you did for record names. Is this recommanded? It makes it difficult to change types, but at least is easy to memorize... So I am wondering how people cope with them, share your opinion, for me the best thing seem to be to try to use one module per big type, and then import qualified x as y, what are good coding practices? A practice I've seen a lot in small- to mid-sized programs is to have a Types module that contains definitions of the types used in the program. ok I will think about it * vector matrices * A thing that bothered me a little was the absence of good standardized vectors and matrices, for now I rolled my own 3x3, I have seen numerical prelude, maybe in the future thre will be a standard interface for matrixes... Rolling my own mattrixes/vectors I have hit against some limitations of classes, nothing terrible, but not so nice, and something that I gather is known for example the fact that you cannot overload + or (in haskell 98) you cannot have overlapping instances. Why not write up your module then send it off to the [EMAIL PROTECTED] mailing list? If this has frustrated you then it's probably frustrated others. Why not contribute something back and polish this problem off? I thought about it, the problem is that I need just a partial implementation of it, but if I will have an enough cleaned and version I will do it. And you can overload (+), just make your matrix type an instance of Num. If some operations shouldn't be supported (like signum, perhaps), the general strategy is just to use error (this is basically due to the fact that Num has too many methods because we don't have a sane way of splitting up type classes. Type class synonyms -- google for them -- look like a good solution, but are lacking an implementation). This is is very ugly in my opinion, because for me a type class should represent something more than just a way to overload, is something is not a number then it should not have the class Num. In this I liked very much the approach of aldor where being an instance of a class is separated from overloading, and must always be explicit, so that a type class can be used also to advertise that something (for example) is commutative and it can have exactly the same functions as another class. Maybe here I should say something explicitly that I realized I had completely forgotten to say: I like haskell very much and I enjoyed using it, but there are some areas where coming from other languages do not seem too well rounded (but maybe it is just that I am not yet fully *in* haskell. by Fawzi ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Haskell Chess
Steffen Mazanek wrote: Hello again, first of all, thank you Don for your help in making hsChess accessible. I have to have a look at darcs and cabal first :-) I have added some more content and a discussion page to the wiki, please contribute your thoughts. Furthermore I added a link to the german project and task description used in the exercises; the English version will be the wiki (although it has no convert2tex function). Best regards, Steffen I stepped onto your mail and found it particularly interesting since I'm currently writing a chess client in Haskell, using GTK+, glade and the nice Cairo library :-). It is called LambdaChess! The code is completely embryonic and totally useless at the moment, but there's a base for a decent GUI interface, with an SVG board, so easily themable. There is also some base code for a PGN file parser written using Parsec, and the whole thing is cabalized. The pieces aren't even drawn yet, but that should be quite easy to do, and I've found a few nice SVG piece sets. The PGN parser doesn't completely parses SAN moves yet, nor does it parse NAG annotations. It doesn't properly validates the presence of the mandatory tags, and so on... I guess I should stop since it's going to be huge if I'm listing all the missing features :-). Ultimately, it'd be nice if this code was able to handle local games between two humans and also playing against the various chess engines (crafty, gnuchess, sjeng, etc...). If it was also able to connect to FICS, it would be the absolute greatness :D. If you or anyone else on this mailing list feels like joining the fun, please do! The code is available here: http://mu.org/~mux/LambdaChess/ Cheers, Maxime ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Haskell Chess
On Mon, 2007-03-19 at 12:14 +0100, Maxime Henrion wrote: I stepped onto your mail and found it particularly interesting since I'm currently writing a chess client in Haskell, using GTK+, glade and the nice Cairo library :-). It is called LambdaChess! Cool! When you have something you want to show off, we could always do with more expositions screen shots etc for the Gtk2Hs website like the things we've got here: http://haskell.org/gtk2hs/archives/category/screenshots/ And I'm glad someone is using the new SVG module that got added in the latest Gtk2Hs release :-) Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Performance Help
Fusing the ws is trickier. Directly appealing to the fibonacci-number example is not recommended because this would mean to keep the last 16 ws in memory and shifting them right to left by hand. But as the Are you saying this because we don't want a 16-tuple? Exactly. Alternate method of computation on the website suggests, you can delegate the shifting to an index that shifts around mod 16. Having a mutable array is helpful, then. Are you saying that because haskell doesn't really have mutable arrays, this is ruled out? Yes, a bit. But you can use ST-arrays if you want. Of course, you can also fill a large static (boxed!) array of 80 Word8s via ws :: Data.Array.IArray.Array Int Word8 ws = accumArray 0 (0,80) (curry snd) $ zip [0..15] xs ++ [(i, xxor i) | i-[16..80]] where xxor i = ws ! (i-16) `xor` ws ! (i-3) `xor` ws ! (i-8) `xor` ws ! (i-14) or something like that (I didn't care about correct indices and bounds). GHC can fuse such array accumulations. Why is an array better than a list? Is it because (!) is O(1) and (!!) is O(n)? In this case, we don't need random access anyway because the 80th element is only available once the previous ones have been calculated. In a sense, lists are perfectly fine. The only point of introducing arrays is that current CPU architecture is optimized to access contiguous blocks of memory and performs much worse on linked lists (besides the fact that lazy evaluation introduces another tiny overhead). Note that the above immutable array has lazy elements as well, so I'm unsure how much benefit they bring. You'd have to try. Maybe it's best to separate the choice between lists and arrays from the actual algorithm with the help of a higher order function that encapsulates the essence of evaluating a recurrence equation. Something like recurrence :: Int - (Int - a) - ((Int - a) - a) - Int - a that satisfies the following laws (beware, they're not suitable for direct implementation) recurrence w start = recurrence w (clip w start) recurrence w start f k | 1 = k k = w = start k | otherwise = f (clip w (\i - recurrence w start f (k-i))) where clip w f = \x - if 1 = x x = w then f x else undefined clips a function to accept only values between 1 and w. This clipping is a bit ad-hoc and you can play various tricks with lightweight dependent types to define functions that are statically known to be defined on the interval [1..w]. For example, the Fibonacci numbers can then be defined as fib n = recurrence 2 (\i - [1,1] !! i) (\g - g 1 + g 2) n In other words, the first higher order argument is the list of starting values and the second higher order arguments is the recurrence equation that defines how to calculate a new element from the 1..w previous ones. Now, you can implement 'recurrence' with lists or arrays or mutable arrays, whatever is fastest. In general, keeping stuff in lists is not wrong, but ByteStrings are more adapted to current CPU and RAM architecture. I'm not clear how ByteStrings help here. We need to put bits into 32 words and operate on these. Ah yes. I think there was some semi-published library of Byte-Strings for any instances of Storable including Word32. Dons knows more. Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Haskell Chess
Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. Maxime, Handling different chess engines isn't hard. chess engine communication is pretty standardized - you would just need to add support for the winboard and/or UCI protocols. FICS is a little bit harder, but it's just a pure test stream over a socket, somewhat like IRC, but less defined. ICC (another chess server) has a slightly better-defined protocol. I can get you more details on any of these protocols (except maybe FICS, which I don't think is documented), if you'd like. By the way, how portable is your graphics code going to be? Sounds like this will be an interesting project. I look forward to it! Andrew On 3/19/07, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-03-19 at 12:14 +0100, Maxime Henrion wrote: I stepped onto your mail and found it particularly interesting since I'm currently writing a chess client in Haskell, using GTK+, glade and the nice Cairo library :-). It is called LambdaChess! Cool! When you have something you want to show off, we could always do with more expositions screen shots etc for the Gtk2Hs website like the things we've got here: http://haskell.org/gtk2hs/archives/category/screenshots/ And I'm glad someone is using the new SVG module that got added in the latest Gtk2Hs release :-) Duncan ___ 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] Haskell Chess
Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. Maxime, Handling different chess engines isn't hard. chess engine communication is pretty standardized - you would just need to add support for the winboard and/or UCI protocols. FICS is a little bit harder, but it's just a pure test stream over a socket, somewhat like IRC, but less defined. ICC (another chess server) has a slightly better-defined protocol. I can get you more details on any of these protocols (except maybe FICS, which I don't think is documented), if you'd like. By the way, how portable is your graphics code going to be? I haven't yet looked in details at the winboard protocol or UCI, but having used crafty and gnuchess in CLI, I have a pretty good idea how this is all working, and this is indeed what I intend to do. As for FICS, I have often played on it through telnet, so I have a good knowledge of this text-based protocol. I don't know of any standard for FICS, but it isn't strictly required to get something working. I'd be interested in ICC support too, but since it's not free, it'll have to wait :-). As for the portability of the my graphics code, I can just say it's GTK+, using Glade XML files, Cairo and SVG on top of Cairo. All of this is supposed to work fine on Windows, if that's what you were asking. I'm not sure about OS X but I think it could also work there. My primary target is UNIX. For those of you who know it, I think BabasChess under Windows sums up what I'd like to obtain in the end quite nicely, features-wise. I'm looking forward receiving your patches! ;-) Cheers, Maxime Sounds like this will be an interesting project. I look forward to it! Andrew On 3/19/07, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-03-19 at 12:14 +0100, Maxime Henrion wrote: I stepped onto your mail and found it particularly interesting since I'm currently writing a chess client in Haskell, using GTK+, glade and the nice Cairo library :-). It is called LambdaChess! Cool! When you have something you want to show off, we could always do with more expositions screen shots etc for the Gtk2Hs website like the things we've got here: http://haskell.org/gtk2hs/archives/category/screenshots/ And I'm glad someone is using the new SVG module that got added in the latest Gtk2Hs release :-) Duncan ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Haskell Chess
Sounds great! I can add patches for ICC, as long as your chess-server code is flexible enough to allow for multiple possible servers. I can also try to do some testing under windows. I think for this to be popular, it will need to work there. As for playing on FICS through telnet...wow, you're a much more patient man than I! On 3/19/07, Maxime Henrion [EMAIL PROTECTED] wrote: Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. Maxime, Handling different chess engines isn't hard. chess engine communication is pretty standardized - you would just need to add support for the winboard and/or UCI protocols. FICS is a little bit harder, but it's just a pure test stream over a socket, somewhat like IRC, but less defined. ICC (another chess server) has a slightly better-defined protocol. I can get you more details on any of these protocols (except maybe FICS, which I don't think is documented), if you'd like. By the way, how portable is your graphics code going to be? I haven't yet looked in details at the winboard protocol or UCI, but having used crafty and gnuchess in CLI, I have a pretty good idea how this is all working, and this is indeed what I intend to do. As for FICS, I have often played on it through telnet, so I have a good knowledge of this text-based protocol. I don't know of any standard for FICS, but it isn't strictly required to get something working. I'd be interested in ICC support too, but since it's not free, it'll have to wait :-). As for the portability of the my graphics code, I can just say it's GTK+, using Glade XML files, Cairo and SVG on top of Cairo. All of this is supposed to work fine on Windows, if that's what you were asking. I'm not sure about OS X but I think it could also work there. My primary target is UNIX. For those of you who know it, I think BabasChess under Windows sums up what I'd like to obtain in the end quite nicely, features-wise. I'm looking forward receiving your patches! ;-) Cheers, Maxime Sounds like this will be an interesting project. I look forward to it! Andrew On 3/19/07, Duncan Coutts [EMAIL PROTECTED] wrote: On Mon, 2007-03-19 at 12:14 +0100, Maxime Henrion wrote: I stepped onto your mail and found it particularly interesting since I'm currently writing a chess client in Haskell, using GTK+, glade and the nice Cairo library :-). It is called LambdaChess! Cool! When you have something you want to show off, we could always do with more expositions screen shots etc for the Gtk2Hs website like the things we've got here: http://haskell.org/gtk2hs/archives/category/screenshots/ And I'm glad someone is using the new SVG module that got added in the latest Gtk2Hs release :-) Duncan ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On Sat, 17 Mar 2007, Philippa Cowderoy wrote: On Sat, 17 Mar 2007, Fawzi Mohamed wrote: So I am wondering how people cope with them, share your opinion, for me the best thing seem to be to try to use one module per big type, and then import qualified x as y, what are good coding practices? http://haskell.org/haskellwiki/Qualified_names http://haskell.org/haskellwiki/Category:Style ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On Mon, 19 Mar 2007, Fawzi Mohamed wrote: A practice I've seen a lot in small- to mid-sized programs is to have a Types module that contains definitions of the types used in the program. ok I will think about it I'd avoid that and suggest a more decentralized design, where each module contributes one main type and according functions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
Quoth Henning Thielemann, nevermore, On Mon, 19 Mar 2007, Fawzi Mohamed wrote: A practice I've seen a lot in small- to mid-sized programs is to have a Types module that contains definitions of the types used in the program. ok I will think about it I'd avoid that and suggest a more decentralized design, where each module contributes one main type and according functions. That sounds like a kind of stateless object-oriented approach. Interesting. I probably do something like that but have never really formalised my thoughts on the matter. Nice one! -- Dougal Stanton ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Haskell Chess
Andrzej, I'd love to hear some of your thoughts on these things. I agree with you about brute-force not being the best approach in haskell (or maybe at all). I think we should switch to haskell-cafe, since that's where much of this discussion has gone, and that's more for extended discussions anyway. On 3/18/07, Andrzej Jaworski [EMAIL PROTECTED] wrote: Didactic it may be but brute force on search trees means in Haskell problem with garbage collection. So students may build a punch but loose a street fight. Instead of using Haskell as a hammer I would rather explore what monadic programming can offer in terms of encapsulating constraints, heuristics, modal logic or agents. Chess is a human game so why not use computing along this line and employ Haskell on humane terms? The force is with us! Cheers, -Andrzej ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On Mar 19, 2007, at 9:56 AM, Henning Thielemann wrote: On Mon, 19 Mar 2007, Fawzi Mohamed wrote: A practice I've seen a lot in small- to mid-sized programs is to have a Types module that contains definitions of the types used in the program. ok I will think about it I'd avoid that and suggest a more decentralized design, where each module contributes one main type and according functions. I'd just like to mention that I've used the central Types module myself on occasion. The main reason is to avoid the need for mutually recursive modules, and not because its a particularly nice design. I try to arrange the user-visible API around some coherent organizing principle, such as the one Henning proposes, but that sometimes leads to module dependency cycles; factoring out a Types module is one way to break the cycles. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
Robert Dockins wrote: On Mar 19, 2007, at 9:56 AM, Henning Thielemann wrote: On Mon, 19 Mar 2007, Fawzi Mohamed wrote: A practice I've seen a lot in small- to mid-sized programs is to have a Types module that contains definitions of the types used in the program. ok I will think about it I'd avoid that and suggest a more decentralized design, where each module contributes one main type and according functions. I'd just like to mention that I've used the central Types module myself on occasion. The main reason is to avoid the need for mutually recursive modules, and not because its a particularly nice design. I try to arrange the user-visible API around some coherent organizing principle, such as the one Henning proposes, but that sometimes leads to module dependency cycles; factoring out a Types module is one way to break the cycles. Rob Dockins I used a Types module for most of the types in the all haskell regex-* backends I wrote. Doing anything else tended to lead to cycles, like Rob mentioned. This seems to be a result of module/import being the one-true-and-unique-way to create a namespace combined with almost no support for recursive modules. Thus data types that (indirectly) refer to each other must be in the same namespace. Thus one cannot even have a all data types go in separate modules policy. As I write the above, I wonder: if a new variant of module that only defines data constructors and types could be created then could compilers support these if they have mutual recursive imports/references? The other alternative being: Make one Types module file that has a new variant of sub-module that defines module namespaces inside the file. This is much that same as concatenating all the separate type modules into a single file. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On Mon, 19 Mar 2007, Chris Kuklewicz wrote: I used a Types module for most of the types in the all haskell regex-* backends I wrote. Doing anything else tended to lead to cycles, like Rob mentioned. This seems to be a result of module/import being the one-true-and-unique-way to create a namespace combined with almost no support for recursive modules. Thus data types that (indirectly) refer to each other must be in the same namespace. Thus one cannot even have a all data types go in separate modules policy. As I write the above, I wonder: if a new variant of module that only defines data constructors and types could be created then could compilers support these if they have mutual recursive imports/references? If I remember correctly, Oberon has one file per module and allows recursive modules. The identifiers to be exported are marked with a '*' on declaration. Interface files are automatically generated from these module files. (And Oberon programmers do not need to maintain export lists.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] There can be only one fix? Pondering Bekic's lemma
On Sat, 17 Mar 2007, Nicolas Frisby wrote: Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x - fix (\y - f (x, y))) = fix f where f :: (a, a) - a The 'fix' on the right hand side is not the standard one (e.g. Control.Monad.Fix), is it? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Summer of Code project proposal
Hi Nikhil, haskell-case is probably a better choice of list for this - haskell is more for announcements. I am Nikhil N, a third year Computer Science student from India. I am looking at building a good IDE for people learning Haskell(as part of SoC).This IDE will be modeled on Dr Scheme or blueJ. Have you looked at something based on HIDE or GuiHaskell? The latter is certainly in the SoC database (I added it), the former was an active project a while ago. How much work do you think is involved in writing an IDE? I suspect its a massive amount - much more than one summers worth Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Lazy IO and closing of file handles
Matthew Brecknell [EMAIL PROTECTED] writes:
Pete Kazmier:
I attempted to read Oleg's fold-stream implementation [1] as this
sounds quite appealing to me, but I was completely overwhelmed,
especially with all of the various type signatures used. It would be
great if one of the regular Haskell bloggers (Tom Moertel are you
reading this?) might write a blog entry or two interpreting his
implementation for those of us starting out in Haskell perhaps by
starting out with a non-polymorphic version so as to emphasize the
approach.
[1] http://okmij.org/ftp/Haskell/fold-stream.lhs
The basic idea of the paper is the use of a left-fold operator as the
primary interface for enumarating collections. The recursive version
(less general than the non-recursive version) of a left-fold operator
for enumerating the lines of a text file might look something like this:
import Control.Monad.Fix
import Control.Exception
import Data.List
import qualified Data.Set as S
import qualified Data.Map as M
import System.IO
enumLines :: (a - String - Either a a) - a - FilePath - IO a
enumLines iter accum filename = do
h - openFile filename ReadMode
flip fix accum $
\iterate accum - do
try_line - try (hGetLine h)
case try_line of
Left e - hClose h return accum
Right line - do
case iter accum line of
Left accum - hClose h return accum
Right accum - iterate accum
I understand the intent of this code, but I am having a hard time
understanding the implementation, specifically the combination of
'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how
one can call 'flip' on a function that takes one argument.
To use this, you provide an iteratee, a function which takes an
accumulator and a line from the file, and returns a new accumulator
embedded in an Either. Using the Left branch causes immediate
termination of the enumeration. For example, to search for the first
occurrence of each of a set of email headers:
getHeaders :: S.Set String - FilePath - IO (S.Set String, M.Map String
String)
getHeaders hdrs file = enumLines findHdrs (hdrs,M.empty) file where
findHdrs accum@(wanted,found) line =
if null line
then Left accum
else
case headerLine line of
Nothing - Right accum
Just hdr -
case findDelete hdr wanted of
Nothing - Right accum
Just wanted -
let accum = (wanted, M.insert hdr line found) in
if S.null wanted
then Left accum
else Right accum
headerLine :: String - Maybe String
headerLine (':':xs) = Just []
headerLine (x:xs) = fmap (x:) (headerLine xs)
headerLine [] = Nothing
findDelete :: Ord a = a - S.Set a - Maybe (S.Set a)
findDelete e s = if S.member e s
then Just (S.delete e s)
else Nothing
It's a bit of a case-analysis nightmare, but when comparing this to
previous approaches, note that file traversal and processing are cleanly
separated, file handle closure is guaranteed to be timely, file
traversal stops as soon as all the required headers have been found,
memory usage is minimised.
Very nice. I like the clean separation, but as you say, its one ugly
bit of code compared to my original code, although much more elegant
no doubt.
I hope that helps.
Very much so. Thank you for you help.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Chess
On Mon, 19 Mar 2007, Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. As a spin-off, will there grow some library for general strategies in board games, like those described in why functional programming matters? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type synonym application
On Sun, Mar 18, 2007 at 05:47:21PM +, C Rodrigues wrote: Type synonyms aren't applied as I would expect during kind checking. What's going on here? type WithList a b = b [a] type FooPair a b = (b, a - b) -- error: `WithList' is applied to too many type arguments ints1 :: WithList Int FooPair [Int] ints1 = ([1], id) That's caused by kind defaulting, as bulat said. -- error: `FooPair' is not applied to enough type arguments ints2 :: (WithList Int FooPair) [Int] ints2 = ([1], id) Type synonyms must be fully applied, i.e. you must always have something like: (FooPair a Int) in types, not just FooPair, (FooPair a) or (FooPair Char). The reason is that otherwise you get type-level lambdas, and type inference becomes undecidable. Thanks Ian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Chess
I originally used a more general approach (probably similar to the one you refer to), but kicked generality out in favor of simplicity. In teaching one should probably just discuss this aspect, but stay with the simple approach (I'll add a note to the wiki page :-)). In contrast, for the real Haskell world such a library would be great. One could even use an abstract game specification and compute the corresponding core (if existing and computation being feasible according to the complexity of the game). Two-Player-zero-sum games are very library friendly kinds of games. However, interesting other games are probably too diverse to be pressed in a general framework, aren't they? Henning Thielemann schrieb: On Mon, 19 Mar 2007, Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. As a spin-off, will there grow some library for general strategies in board games, like those described in why functional programming matters? ___ 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
[Haskell-cafe] Re: what I learnt from my first serious haskell programm
Robert Dockins wrote: The main reason is to avoid the need for mutually recursive modules, and not because its a particularly nice design. Chris Kuklewicz wrote: This seems to be a result of module/import being the one-true-and-unique-way to create a namespace combined with almost no support for recursive modules. I'd like to remind you that the Haskell98 report explicitly allows recursive modules http://haskell.org/onlinereport/modules.html However, it's a real pity that Hugs doesn't support them at all and that you have to take extra pains with .boot-files to get them in GHC. Recursive modules are the lazy evaluation of modules and One should not obstruct access to such a vital tool. I want recursive modules for free! Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Haskell Chess
Hi Andrew, and thank you for invitation. Well, what can I say. I am glad that the wise game can spark spirit of cooperation here. Perhaps it is time for Mr. Haskell to leave stale university rooms and go out for beer:-) On my part I can promise to watch the project and perhaps, architecture permitting, I may suggest a module that could learn from mistakes. Cheers, -Andrzej ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Chess
Here's my take on this: I've thought for a while now that Haskell needs a general toolkit for AI. After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. Anyway, my suggestion would be to concentrate on methods of AI. For example, if we implement alpha-beta polymorphically enough, it should be trivial to use it for any game that it makes sense to use it on. This kind of thing is what I was thinking of when I talked about some fundamental design ideas I had. Things like writing a Board type-class, so that you can implement any board representation you want to for chess. Or writing alpha-beta in terms of positions and moves, regardless of what kind of game you're talking about (I also think you simply must use unfoldTree, as this is a beautiful instance of it). Things like learning, and other general strategies, should be developed independently of any particular game, IMHO. On 3/19/07, Steffen Mazanek [EMAIL PROTECTED] wrote: I originally used a more general approach (probably similar to the one you refer to), but kicked generality out in favor of simplicity. In teaching one should probably just discuss this aspect, but stay with the simple approach (I'll add a note to the wiki page :-)). In contrast, for the real Haskell world such a library would be great. One could even use an abstract game specification and compute the corresponding core (if existing and computation being feasible according to the complexity of the game). Two-Player-zero-sum games are very library friendly kinds of games. However, interesting other games are probably too diverse to be pressed in a general framework, aren't they? Henning Thielemann schrieb: On Mon, 19 Mar 2007, Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. As a spin-off, will there grow some library for general strategies in board games, like those described in why functional programming matters? ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] There can be only one fix? Pondering Bekic's lemma
Nope, but I believe the two are equipotent. This usage of believe is one of those I think I remember reading it somewhere usages. On 3/19/07, Henning Thielemann [EMAIL PROTECTED] wrote: On Sat, 17 Mar 2007, Nicolas Frisby wrote: Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x - fix (\y - f (x, y))) = fix f where f :: (a, a) - a The 'fix' on the right hand side is not the standard one (e.g. Control.Monad.Fix), is it? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type synonym application
On Mon, 19 Mar 2007, Ian Lynagh wrote: On Sun, Mar 18, 2007 at 05:47:21PM +, C Rodrigues wrote: Type synonyms aren't applied as I would expect during kind checking. What's going on here? type WithList a b = b [a] type FooPair a b = (b, a - b) -- error: `WithList' is applied to too many type arguments ints1 :: WithList Int FooPair [Int] ints1 = ([1], id) That's caused by kind defaulting, as bulat said. In Haskell 98 it is not allowed to define type synonymes in a partially applied manner. That is, there is no alternative to type WithList a b c = b [a] c ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On 19/03/07, Fawzi Mohamed [EMAIL PROTECTED] wrote: This is is very ugly in my opinion, because for me a type class should represent something more than just a way to overload, is something is not a number then it should not have the class Num. Num is a collection of types whose members can be added and subtracted and so on. As numbers are the most common example of this, one could say the members of Num _act like numbers_, rather than are numbers in themselves. Really typeclasses are all about overloading. For example, Eq is the collection of types that the equality predicate (==) applies to. I don't see this as ugly; quite the contrary, in that if you know a type instantiates Eq you can use (==) without worrying about using a type-specific equality predicate. E.g. it's nice to see the same (==) everywhere rather than seeing (say) (Int.==), (Bool.==) and so on. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Search monad
Hey, I have a structure containing Xs in various places, like so data X data Structure = Structure .. [X] .. [X] .. And I defined mapStructure mapStructure :: (X - X) - (Structure - Structure) I then wanted to use mapStructure to define queries as well as transformations on structures. I generalized mapStructure to mapStructureM: mapStructure :: Monad m = (X - m X) - (Structure - m Structure) and then defined the following search monad: data Search f a b = Found (f a) b class Monad (m a) = SearchMonad m a where found :: a - m a a fromSearch :: Search f a b - f a fromSearch (Found a _) = a search :: (SearchMonad m a) = (a - Bool) - a - m a a search f a | f a = found a | otherwise = return a Instances of the monad for finding one and for finding all elements: instance SearchMonad (Search Maybe) a where found a = Found (Just a) a instance SearchMonad (Search []) a where found a = Found [a] a instance Monad (Search Maybe a) where return b = Found Nothing b Found (Just a) a' = f = case f a' of Found _ b - Found (Just a) b Found Nothing a' = f = f a' instance Monad (Search [] a) where return b = Found [] b Found as a' = f = case f a' of Found as' b - Found (as ++ as') b Here is a simple sample session with ghci *Util fromSearch $ mapM (search even) [1,3,5] :: Maybe Int Nothing *Util fromSearch $ mapM (search even) [1,2,3,4,5] :: Maybe Int Just 2 *Util fromSearch $ mapM (search even) [1,2,3,4,5] :: [Int] [2,4] What I'm wondering about is if this monad is an instance of a more general monad(if so, which one?), and generally if people have any comments about these definitions. Thanks! Edsko ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: MIME Strike Force
Jeremy Shaw wrote: Hello, If you have tried to do any MIME processing using Haskell, you are likely to have found two things: 1) There are a lot of MIME libraries for Haskell 2) None of them do everything you want So, I propose that we form a MIME Strike Force and create the one, true MIME library. The plan is something like this: 1) Document all the things the MIME library needs to support. 2) Pick the technology, and design the infrastructure for supporting these features. For example, I don't think we will be able to use Parsec because: i) We want to support ByteString ii) We want to be able to lazily parse the message 3) Try to reuse as much existing code as possible to implement the design. I have started step 1 by creating this page: http://www.haskell.org/haskellwiki/Libraries_and_tools/MIMEStrikeForce Please add your comments, requirements, etc. If you are interesting in helping contrib ideas, code, or flames, please let me know. If there is enough interest, we should probably set up a mailing list for discussion. j. ps. This *might* make a decent SoC project, but only if it results in the one, true MIME library. We definitely do not need another incomplete MIME library floating around. Good idea! I added a subsection for existing code to the wiki page, and added the multipart parser from the cgi package, which uses ByteStrings. /Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
David House wrote: On 19/03/07, Fawzi Mohamed [EMAIL PROTECTED] wrote: This is is very ugly in my opinion, because for me a type class should represent something more than just a way to overload, is something is not a number then it should not have the class Num. Num is a collection of types whose members can be added and subtracted and so on. As numbers are the most common example of this, one could say the members of Num _act like numbers_, rather than are numbers in themselves. Really typeclasses are all about overloading. For example, Eq is the collection of types that the equality predicate (==) applies to. I don't see this as ugly; quite the contrary, in that if you know a type instantiates Eq you can use (==) without worrying about using a type-specific equality predicate. E.g. it's nice to see the same (==) everywhere rather than seeing (say) (Int.==), (Bool.==) and so on. Maybe I did not express me clearly enough, I think that classes are useful (and the language that I was speaking of, aldor, has them), but it is not nice that the only way to have an overloaded function is to define a type class, or that you need to fully implement a class just to overload one function of it. Vectors don't act like numbers, a vector space is not a field, even if they have some common operations. I find it misleading to define something a number when it does not satisfy all the properties of numbers. The numerical prelude might fix this, but still I think that class and overloading should be distinct concepts. Fawzi ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Lazy IO and closing of file handles
Pete Kazmier [EMAIL PROTECTED] writes: I attempted to read Oleg's fold-stream implementation [1] as this sounds quite appealing to me, but I was completely overwhelmed, especially with all of the various type signatures used. It would be great if one of the regular Haskell bloggers (Tom Moertel are you reading this?) might write a blog entry or two interpreting his implementation for those of us starting out in Haskell perhaps by starting out with a non-polymorphic version so as to emphasize the approach. [1] http://okmij.org/ftp/Haskell/fold-stream.lhs In the event any other Haskell newbie comes along someday and is just as overwhelmed as I was, I've found this post by Oleg to be a much easier to understand than the above paper because it is not as generic and thus the type signatures are a bit easier on the eyes: http://www.haskell.org/pipermail/haskell/2003-September/012741.html With that said, I have a question regarding Hal's response to the above email in which he states: Just thought I'd mention that this is, in fact, my preferred method of iterating over a file. It alleviates the pain associated with lazy file IO, and simultaneously provides a useful abstraction. I actually have 3*2 functions that I use which look like: type Iteratee iter seed = seed - iter - Either seed seed hFoldChars :: FilePath - Iteratee Char seed - seed - IO seed hFoldLines :: FilePath - Iteratee String seed - seed - IO seed hFoldWords :: FilePath - Iteratee [String] seed - seed - IO seed type IterateeM iter seed = seed - iter - IO (Either seed seed) hFoldCharsM :: FilePath - IterateeM Char seed - seed - IO seed hFoldLinesM :: FilePath - IterateeM String seed - seed - IO seed hFoldWordsM :: FilePath - IterateeM [String] seed - seed - IO seed Which perform as expected (hFoldWords(M) can be written in terms of hFoldLinesM, but I find I use it sufficiently frequently to warrent having it stand out). Also, of course, the only ones actually implemented are the (M) variants; the non-M variants just throw a return into the Iteratee. What does he mean by the very last sentence? Oleg's version seems more like the non-M versions. What is his implication? Thanks, Pete ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Chess
Same as the MIME case: http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdfhttp://web.engr.oregonstate.edu/%7Eerwig/papers/Zurg_JFP04.pdf http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdfhttp://www.cs.rutgers.edu/%7Eccshan/logicprog/LogicT-icfp2005.pdf http://web.cecs.pdx.edu/~apt/jfp01.pshttp://web.cecs.pdx.edu/%7Eapt/jfp01.ps http://www.cs.yale.edu/homes/cc392/report.html It would be great trying to unify all of these (and many more) into a library. Following he AIMA structure could be a good start. At the moment I'm working on implementing some AI Planning systems in Haskell and wrote my own logic unification, for example. On 3/19/07, Andrew Wagner [EMAIL PROTECTED] wrote: Here's my take on this: I've thought for a while now that Haskell needs a general toolkit for AI. After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. Anyway, my suggestion would be to concentrate on methods of AI. For example, if we implement alpha-beta polymorphically enough, it should be trivial to use it for any game that it makes sense to use it on. This kind of thing is what I was thinking of when I talked about some fundamental design ideas I had. Things like writing a Board type-class, so that you can implement any board representation you want to for chess. Or writing alpha-beta in terms of positions and moves, regardless of what kind of game you're talking about (I also think you simply must use unfoldTree, as this is a beautiful instance of it). Things like learning, and other general strategies, should be developed independently of any particular game, IMHO. On 3/19/07, Steffen Mazanek [EMAIL PROTECTED] wrote: I originally used a more general approach (probably similar to the one you refer to), but kicked generality out in favor of simplicity. In teaching one should probably just discuss this aspect, but stay with the simple approach (I'll add a note to the wiki page :-)). In contrast, for the real Haskell world such a library would be great. One could even use an abstract game specification and compute the corresponding core (if existing and computation being feasible according to the complexity of the game). Two-Player-zero-sum games are very library friendly kinds of games. However, interesting other games are probably too diverse to be pressed in a general framework, aren't they? Henning Thielemann schrieb: On Mon, 19 Mar 2007, Andrew Wagner wrote: Steffen, I've done some chess AI programming in the past, so I'd be happy to help with this project. I have some pretty fundamental design suggestions that I'll write up for the wiki page. As a spin-off, will there grow some library for general strategies in board games, like those described in why functional programming matters? ___ 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ricardo Guimarães Herrmann Any sufficiently complicated C or Fortran program contains an ad hoc, informally specified, bug-ridden, slow implementation of half of Common Lisp Any sufficiently complicated Lisp or Ruby program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: what I learnt from my first serious haskell programm
Fawzi Mohamed [EMAIL PROTECTED] writes: Vectors don't act like numbers, a vector space is not a field, even if they have some common operations. That's a long-standing flaw in the design of numeric classes. It's not a problem with typeclasses per se. I find it misleading to define something a number when it does not satisfy all the properties of numbers. Justifiably so. But if you had a class Additive, would you be unhappy about defining (+) on non-numbers? The numerical prelude might fix this, but still I think that class and overloading should be distinct concepts. I think the problem here is that you are using the word class to mean something different from Haskell classes. Haskell typeclasses /are/ overloading, and that's what I understand them as. They were originally introduced as a solution to the question of how to handle equality so that one didn't have to use different names for the same concept on different types. -- Jón Fairbairn [EMAIL PROTECTED] http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2006-09-13) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell and AI
I agree with Andrew Wagner re: Haskell and AI. There are some relevant resources on Haskell, Maths, and Logic: *The Haskell Road To Logic, Maths And Programming (Paperback) * by Kees Doets http://www.amazon.com/exec/obidos/search-handle-url/103-5196905-1677457?%5Fencoding=UTF8search-type=ssindex=booksfield-author=Kees%20Doets (Author), Jan van Eijck http://www.amazon.com/exec/obidos/search-handle-url/103-5196905-1677457?%5Fencoding=UTF8search-type=ssindex=booksfield-author=Jan%20van%20Eijck (Author) http://www.amazon.com/Haskell-Road-Logic-Maths-Programming/dp/0954300696/ref=sr_1_1/103-5196905-1677457?ie=UTF8s=booksqid=1174327994sr=1-1 van Eijck has another book on Computational Semantics. Elsewhere, there is work on learning algorithms in Haskell. Broadly, we might start by gathering known resources, projects, and people. We could consider one of the standard AI books as a guide for chapters, sections, and problems to fill in with Haskell approaches. I'd be very interested to contribute to this. Cheers, Adam Wyner Message: 7 Date: Mon, 19 Mar 2007 12:51:19 -0400 From: Andrew Wagner [EMAIL PROTECTED] Subject: Re: [Haskell-cafe] Haskell Chess To: haskell-cafe@haskell.org Message-ID: [EMAIL PROTECTED] Content-Type: text/plain; charset=ISO-8859-1; format=flowed Here's my take on this: I've thought for a while now that Haskell needs a general toolkit for AI. After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. Anyway, my suggestion would be to concentrate on methods of AI. For example, if we implement alpha-beta polymorphically enough, it should be trivial to use it for any game that it makes sense to use it on. This kind of thing is what I was thinking of when I talked about some fundamental design ideas I had. Things like writing a Board type-class, so that you can implement any board representation you want to for chess. Or writing alpha-beta in terms of positions and moves, regardless of what kind of game you're talking about (I also think you simply must use unfoldTree, as this is a beautiful instance of it). Things like learning, and other general strategies, should be developed independently of any particular game, IMHO. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: System.Random StdGen read fails on some strings? [also continues: Random/StdGen/read: there is something unclear (or misunderstood!)]
On 3/19/07, Simon Peyton-Jones [EMAIL PROTECTED] wrote: Zara Good point. It's a bit stupid that 'read' fails utterly on strings shorter than 6. I don't thin StdRandom has an owner at the moment. There's a process for proposing library changes, described under guidelines for developers here http://haskell.org/haskellwiki/Libraries_and_tools That's the way to get your change adopted. There's already a thread about this on the libraries list: http://www.haskell.org/pipermail/libraries/2007-March/007052.html Ian commented with a proposal for fixing it, and no one has followed up yet. That would probably be a good place to direct any more discussion. Cheers, Kirsten ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Lazy IO and closing of file handles
Pete Kazmier wrote: I understand the intent of this code, but I am having a hard time understanding the implementation, specifically the combination of 'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how one can call 'flip' on a function that takes one argument. If you look at the code, that's not really what's happening. See the embedded anonymous function below? flip fix accum $ \iterate accum - do ... It's a function of two arguments. All flip is doing is switching the order of the arguments to fix, in this case for readability. If you were to get rid of the flip, you'd need to remove the accum after fix and move it after the lambda expression, which would make the expression much uglier to write and read. So all the flip is doing here is tidying up the code. (If you're still confused, look at the difference between forM and mapM. The only reason forM exists is readability when you have - in terms of the amount of screen space they consume - a big function and a small piece of data, just as here.) As to why it's okay to call flip on fix at all, look at the types involved. fix :: (a - a) - a flip :: (a - b - c) - b - a - c By substitution: flip fix :: a - ((a - b) - a - b) - b In the case above, accum has type a, and the lambda has type (a - IO a) - a - IO a, and these fit nicely into the type expected by flip fix. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell and AI
I agree with Andrew Wagner re: Haskell and AI. There are some relevant resources on Haskell, Maths, and Logic: The Haskell Road To Logic, Maths And Programming (Paperback) by Kees Doets (Author), Jan van Eijck (Author) http://www.amazon.com/Haskell-Road-Logic-Maths-Programming/dp/0954300696/ref=sr_1_1/103-5196905-1677457?ie=UTF8s=booksqid=1174327994sr=1-1 I liked this book. What parts did you have in mind specifically as being relevant to AI? van Eijck has another book on Computational Semantics. Elsewhere, there is work on learning algorithms in Haskell. Broadly, we might start by gathering known resources, projects, and people. We could consider one of the standard AI books as a guide for chapters, sections, and problems to fill in with Haskell approaches. I like this idea. On the other thread [1] Ricardo Herrmann suggested following the structure of AI: A Modern Approach, the classical text [2] by Russell and Norvig. Do others agree? I think we should carve out a section of the wiki, in the Applications and Libraries section [3] for AI, which should then be split into (at least) a section each for relevant papers, code, interesting AI problems with their solutions, and a table-of-contents type page, structured according to a text like this. Comments? I'd be very interested to contribute to this. Maybe we should assemble an AI strike force? :) Cheers, Adam Wyner [1] http://www.haskell.org/pipermail/haskell-cafe/2007-March/023646.html [2] http://aima.cs.berkeley.edu/ [3] http://www.haskell.org/haskellwiki/Libraries_and_tools ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Search monad
Hello, You might want to look at the scrap your boilerplate papers and/or their implementation in GHC in Data.Generics. -Jeff [EMAIL PROTECTED] wrote on 03/19/2007 01:11:19 PM: Hey, I have a structure containing Xs in various places, like so data X data Structure = Structure .. [X] .. [X] .. And I defined mapStructure mapStructure :: (X - X) - (Structure - Structure) I then wanted to use mapStructure to define queries as well as transformations on structures. I generalized mapStructure to mapStructureM: mapStructure :: Monad m = (X - m X) - (Structure - m Structure) and then defined the following search monad: data Search f a b = Found (f a) b class Monad (m a) = SearchMonad m a where found :: a - m a a fromSearch :: Search f a b - f a fromSearch (Found a _) = a search :: (SearchMonad m a) = (a - Bool) - a - m a a search f a | f a = found a | otherwise = return a Instances of the monad for finding one and for finding all elements: instance SearchMonad (Search Maybe) a where found a = Found (Just a) a instance SearchMonad (Search []) a where found a = Found [a] a instance Monad (Search Maybe a) where return b = Found Nothing b Found (Just a) a' = f = case f a' of Found _ b - Found (Just a) b Found Nothing a' = f = f a' instance Monad (Search [] a) where return b = Found [] b Found as a' = f = case f a' of Found as' b - Found (as ++ as') b Here is a simple sample session with ghci *Util fromSearch $ mapM (search even) [1,3,5] :: Maybe Int Nothing *Util fromSearch $ mapM (search even) [1,2,3,4,5] :: Maybe Int Just 2 *Util fromSearch $ mapM (search even) [1,2,3,4,5] :: [Int] [2,4] What I'm wondering about is if this monad is an instance of a more general monad(if so, which one?), and generally if people have any comments about these definitions. Thanks! Edsko ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Algorithms
P. R. Stanley wrote: yes, this is good. So, let's start with A. How would you sope the problem? What's your algorithm for identifying problems? What is understanding? Discuss... To relate a problem to known problems, I think I use a heuristic search that may bite the bullet and do a brute-force search. The search is on both the target problem and the relation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Lazy IO and closing of file handles
Here's what happens: fix has type (x-x)-x and that has to match the first argument to flip, namely 'a-b-c'. The only chance of that is if x is actually a function type. Pick x=b-c, now we have fix has type ((b-c)-b-c)-b-c and it matches a-b-c if a=(b-c)-b-c Flip returns b-a-c, and if we substitute we get b-((b-c)-b-c)-c If you rename the variables you get the suggested type. -- Lennart On Mar 19, 2007, at 20:35 , Pete Kazmier wrote: Bryan O'Sullivan [EMAIL PROTECTED] writes: Pete Kazmier wrote: I understand the intent of this code, but I am having a hard time understanding the implementation, specifically the combination of 'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how one can call 'flip' on a function that takes one argument. As to why it's okay to call flip on fix at all, look at the types involved. fix :: (a - a) - a flip :: (a - b - c) - b - a - c By substitution: flip fix :: a - ((a - b) - a - b) - b Sadly, I'm still confused. I understand how 'flip' works in the case where its argument is a function that takes two arguments. I've started to use this in my own code lately. But my brain refuses to understand how 'flip' is applied to 'fix', a function that takes one argument only, which happens to be a function itself. What is 'flip' flipping when the function passed to it only takes one argument? Thanks, Pete ___ 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: Lazy IO and closing of file handles
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Pete Kazmier wrote: Bryan O'Sullivan [EMAIL PROTECTED] writes: Pete Kazmier wrote: I understand the intent of this code, but I am having a hard time understanding the implementation, specifically the combination of 'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how one can call 'flip' on a function that takes one argument. As to why it's okay to call flip on fix at all, look at the types involved. fix :: (a - a) - a flip :: (a - b - c) - b - a - c By substitution: flip fix :: a - ((a - b) - a - b) - b Sadly, I'm still confused. I understand how 'flip' works in the case where its argument is a function that takes two arguments. I've started to use this in my own code lately. But my brain refuses to understand how 'flip' is applied to 'fix', a function that takes one argument only, which happens to be a function itself. What is 'flip' flipping when the function passed to it only takes one argument? fix :: (a - a) - a In this case, we know something about 'a': it is a function (b - c). Substitute: fix :: ((b - c) - (b - c)) - (b - c) Take advantage of the right-associativity of (-) fix :: ((b - c) - b - c) - b - c Now it looks like a function of two arguments, because the return value (normally ordinary data) can in fact, in this case, take arguments. Here's another example of that: data Box a = Box a get (Box a) = a - -- get (Box 1) :: Int - -- get (Box (\a - a)) :: Int - Int - -- (get (Box (\a - a))) 1 :: Int --function application is left-associative: - -- get (Box (\a - a)) 1 :: Int - -- flip get 1 (Box (\a - a)) :: Int Yes, it sometimes confuses me too. Isaac -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.3 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFF/vcXHgcxvIWYTTURAj5RAKCUMeAF0vosJ6ROAVlBIDHsEq/vzgCfflnR 50BmW6tuAF6mKXBtrlHdQ5Y= =uv3G -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] There can be only one fix? Pondering Bekic's lemma
Nicolas Frisby wrote:
My question is: Given products and a fixed point combinator, can any
pure expression be transformed into a corresponding expression that
has just a single use of fix?
If yes, has there been any usage of such a transformation, or is it just
crazy?
Yes.
One use is theoretical and conscious. Facts proven about single
recursion automatically carry over to mutual recursions, since the
latter can be packaged up as the former. For example, one fact says that
regarding the equation x = f x, you can construct the sequence
_|_, f _|_, f (f _|_), ..., f^n _|_, ...
the terms get closer to a solution for x as you go down the sequence,
and under a continuity assumption, you just need omega iterations to get
to the fixed point. The same fact automatically applies to the system of
equations {y = g z, z = h y}, i.e., the sequence
(_|_, _|_), (g_|_, h_|_), (g (h_|_), h (g_|_)), ...
gets closer and closer to a solution for (y,z), and under a continuity
assumption you just need omega iterations to get to the solution. This
is of course the most basic example of facts. There are more advanced
facts, such as fusion, leapfrogging, etc. with practical use in code
optimization, and they are enjoyed by both single recursion and mutual
recursion.
(Perhaps it is now clear what is meant by true product and why it is
required. The above example fact says in general: start your sequence
from the bottom. This bottom seems a bit ambiguous in the mutual case,
since there are two different common ways of tupling up two partial
orders. One is the cartesian product, which you probably know how to do,
and its bottom is (_|_, _|_). The other is, on top of that --- or shall
I say below bottom of that --- insert an extra _|_ below (_|_, _|_), and
this is what Haskell 98 does with its (,) type. Clearly, for our theory
to work, you want the former, and its probably called the true product
in contrast to the latter, which is the lifted product or pointed
product.)
But perhaps the most widespread practical use is a subconscious one. How
do you write an interpreter, for a language that supports mutual
recursion, in a language that just provides iteration? You introduce a
program counter and a stack, then you write just one loop: it
dereferences the program counter, does a case analysis, updates stack as
necessary, updates program counter as necessary, repeat. You have turned
a mutual recursion into a single tail recursion. In an indirect sense it
is an application of the basic example theoretical fact above. It is so
widespread and yet so subconscious, you cannot avoid it if you use any
real computer at all, and yet you hardly think about it, as this is
exactly what every existing CPU does.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Two Other AI Sources
For the Haskell and AI work, we ought to consider AI programming books in addition to Russell and Norvig: /Paradigms of AI Programming: Case Studies in Common Lisp/, P. Norvig, 1991. /Prolog Programming for Artificial Intelligence/, I. Bratko, 1990./ Artificial Intelligence Techniques in Prolog/, Y. Shoham, 1994. Perhaps there are newer additions (e.g. Bratko), but the problems and solutions from these languages are presented. We can build on them rather than starting from scratch or even just the theoretical outline of Russell and Norvig. Adam ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] what I learnt from my first serious haskell programm
Hello Fawzi, Monday, March 19, 2007, 8:26:33 PM, you wrote: Maybe I did not express me clearly enough, I think that classes are useful (and the language that I was speaking of, aldor, has them), but it is not nice that the only way to have an overloaded function is to define a type class overloading without using type classes (as it is implemented in C++) is hardly compatible with type inference. imagine that you has two functions: f :: String - Int f :: Int - Int and write (f a). what should be type of a? it becomes a list of possible types. because type inference mechanism pushes inferred types up and down, the whole information about type of each term will become much more complicated. compare this to current requirement to overload using only type classes. in this case, you know that 'a' belongs to some class, so possible variants don't multiply at each inference step -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] what I learnt from my first serious haskell programm
Hello Fawzi, Monday, March 19, 2007, 1:20:37 PM, you wrote: Also arrays, inset,... have quite some overlapping. For array the use of the IArray typeclass kept the things nice also using Arrays and UArrays together, but adding IntSet to the whole worked only qualifying, and then I also wanted to define a fold for my type... there are two libraries, Edison and Collection, that includes type classes hierarchy for collection types. may be, it will be useful for you -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] what I learnt from my first serious haskell programm
On 19/03/07, Fawzi Mohamed [EMAIL PROTECTED] wrote: Vectors don't act like numbers, a vector space is not a field, even if they have some common operations. As I said in my previous email, this is because Num is too big. We need to split it down, but there's no sane way of doing this without your average numeric function needing about a thousand different constraints on it. Type class synonyms [1] look promising, but no-one's implemented them yet AFAIK. [1]: http://repetae.net/john/recent/out/classalias.html -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
Pete Kazmier: I understand the intent of this code, but I am having a hard time understanding the implementation, specifically the combination of 'fix', 'flip', and 'interate'. I looked up 'fix' and I'm unsure how one can call 'flip' on a function that takes one argument. I threw that in there because I figured you were up for another challenge. :-) It took me ages to get some clue about how to use fix, quite apart from combining it with flip. The concept of passing the output of a function as one of its parameters (tying the knot) can be difficult to accept, particularly if you haven't studied lambda calculus. Note that I could have just written this: let iterate a = do ... iterate a' ... iterate accum Or this: fix iterate accum where iterate a = do ... iterate a' ... Though with the latter, I presume you would still be confused about how I can pass two arguments to a function that only takes one. Actually, that's not that difficult. Say I have a function f that takes two arguments. Then I could write: (id f) a b No problem. But function application associates to the left (at least in value-land), so I could just as easily write: id f a b You could say I was passing three arguments to id, which only takes one argument. But id returns its first argument, so I'm really just passing the last two arguments to the function returned by id. So with my use of flip fix, I'm really just calling fix on the anonymous function (\iterate accum - ...), and then the parameter (accum) is passed to the function returned by fix. So now you just need a couple of weeks (or months if you're as slow as me) to understand what fix is all about... :-) There is the question of whether it's preferable to use the let form or the fix form for embedding a recursive function in the middle of a do-block. I don't know if there's any consensus on this question, but it seems to me to be about whether one prefers to read a function top-down or bottom-up. I think I'm about 80/20 top-down/bottom-up. When I read a let, I know (due to laziness) that it doesn't have any effect until the bindings are used, so I usually find myself scanning forward to find those uses. When I read fix \f - ..., I see exactly how the (anonymous) function is used, just before I get to its definition. So fix helps me to see things in a mostly top-down fashion. A couple of times I have wished that the libraries contained pre-flipped versions of fix, for example: fix1 a f = fix f a fix2 a b f = fix f a b fix3 a b c f = fix f a b c Any opinions on whether this would be a worthwhile addition? Or would it just legitimise an obscure idiom? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and AI
From: Andrew Wagner [EMAIL PROTECTED] After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. A small observation that might or might not be useful for implementing game AIs: 2 player games and their strategies form a monad in a non-trivial way. http://sigfpe.blogspot.com/2006/10/games-strategies-and-self-composition.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Matrices in Haskell
Some of you might recall me annoying people on #haskell over the New Year about my Latin Squares project. Well, I'm looking at re-doing it from scratch, but the first thing I need to do is find a new way of representing my square. I have been using a list of lists ([[a]]) to represent a matrix. The problem with this data structure is that I need to be able to manipulate matrices as both row-oriented and column-oriented data structures, as I need to examine the values in the columns as well as in the rows. As it stands, I was doing this by transposing the matrix, manipulating it, then transposing it back again. This is a pain, as it takes up about 15% to 20% of the run time. The other problem with using a list of lists is that the only reason I'm sure that the matrix is valid (i.e. all the rows are the same length, etc.) is because I created it that way, not because the data structure requires it. As such, I'd like to know if there's any way of storing a an n-by-n matrix such that the algorithm/function to get either the rows or the columns is less than O(n^2) like transposition is. I did try using an Array, but my (admittedly hurried and naive) usage of them took longer than a list of lists, was more difficult to manipulate, and wasn't required separate inverse functions to row and cols. Also, since I need to look all throughout the list of values, it's still O(n^2), but this time for both rows and columns. I know that when doing something similar to this in Java a few years ago (a primitive Sudoku solver, to be precise), I could represent the rows and columns as to separate 2D arrays, with rows(i,j) pointing to the same object as cols(j,i). Is something like this possible in Haskell? in particular, I will be storing lists of possible values in the cells of the matrix, so the capability to backtrack would be very nice, as I'd be trying each value at a time to see if it is valid. I'd also want to use such a matrix implementation next semester for a project, which I plan on being a quick comparison of various programming languages as to ease of use and efficiency for matrix-based computing problems. -- Ivan Lazar Miljenovic ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: N and R are categories, no?
Thanks! Somehow, the, now blindingly obvious, fact that a monad must be a mapping into (not onto, right, at least in general?) is something I had missed, although it did lead me to be puzzled about join. So, although you could have a functor from N to R, there is no way it could be a monad. In Haskell, it would be Integer instead of N, since the category we deal with for Haskell Monads are Haskell types. Does a typeclass, like Num or Eq, form a category? I know that you can't restrict an instance of Monad to be only over a particular typeclass, but could I have an EqMonad, with all of the non-sugar properties of Monad? On 3/15/07, Ulf Norell [EMAIL PROTECTED] wrote: On 3/15/07, Steve Downey [EMAIL PROTECTED] wrote: EOk, i'm trying to write down, not another monad tutorial, because I don't know that much yet, but an explication of my current understanding of monads. But before I write down something that is just flat worng, I thought I'd get a cross check. (and I can't get to #haskell) Monads are Functors. Functors are projections from one category to another such that structure is preserved. One example I have in mind is the embedding of the natural numbers into the real numbers. The mapping is so good, that we don't flinch at saying 1 == 1.0. Monads are endofunctors (functors from one category to itself). This is easy to see from the type of join: join : m (m a) - m a For Haskell monads the category is the category of Haskell types and Haskell functions. In this category N and R are objects, so you'll get the wrong idea trying to see them as categories. / Ulf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and AI
Hi Dan, I just made the connection between you and your blog, by the way - great stuff, keep it up. This particular blog is fascinating, too, but I'm not sure how useful it is to look at more complex 2-player games this way. I'll have to think about it some more On 3/19/07, Dan Piponi [EMAIL PROTECTED] wrote: From: Andrew Wagner [EMAIL PROTECTED] After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. A small observation that might or might not be useful for implementing game AIs: 2 player games and their strategies form a monad in a non-trivial way. http://sigfpe.blogspot.com/2006/10/games-strategies-and-self-composition.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: N and R are categories, no?
Thanks. I am trying to develop some intuition / understanding of monads outside category Fun, because I suspect that once I do, they will be both simpler and more interesting. I think if I take the category N to be the natural numbers and the algebraic functions of a single variable to be the arrows, then the functor that takes n to 2n might be a monad. That is, a coordinate transform should be monadic. -smd On 3/15/07, Nicolas Frisby [EMAIL PROTECTED] wrote: That said, N and R are indeed categories; however, considering them as categories should be carefully interlaced with your intuitions about them as types. I haven't formally checked it, but I would bet that this endofunctor over N, called Sign, is a monad: Sign x = x + x Pos = injectLeft Neg = injectRight unit = Pos join (Pos (Pos n)) = Pos n join (Pos (Neg n)) = Neg n join (Neg (Pos n)) = Neg n join (Neg (Neg n)) = Pos n Pos and Neg are just labels for sign. I'm assuming N is the naturals, not the integers; thus this monad might actually be useful :). Also note that this means there is not necessarily a mapping from F x - x. Neg 3 should not necessarily map to 3. Also, this structure is probably satisfies many more laws than just the monad laws--e.g. monoids or monoidals. So while it might not always make sense to consider N and R as categories when learning about category theory and Haskell, it might be helpful to learn about monads (and other notions) in categories simpler than the Fun category of functional types and partial functions--N and R are could be good categories for such learning. Have fun! On 3/15/07, Ulf Norell [EMAIL PROTECTED] wrote: On 3/15/07, Steve Downey [EMAIL PROTECTED] wrote: EOk, i'm trying to write down, not another monad tutorial, because I don't know that much yet, but an explication of my current understanding of monads. But before I write down something that is just flat worng, I thought I'd get a cross check. (and I can't get to #haskell) Monads are Functors. Functors are projections from one category to another such that structure is preserved. One example I have in mind is the embedding of the natural numbers into the real numbers. The mapping is so good, that we don't flinch at saying 1 == 1.0. Monads are endofunctors (functors from one category to itself). This is easy to see from the type of join: join : m (m a) - m a For Haskell monads the category is the category of Haskell types and Haskell functions. In this category N and R are objects, so you'll get the wrong idea trying to see them as categories. / Ulf ___ 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
[Haskell-cafe] Re: N and R are categories, no?
Picky is good, because it helps me realize things like I haven't been paying enough attention to unit and join. Other than realizing that they make the box diagram and triangle diagram commute. -smd On 3/15/07, Dominic Steinitz [EMAIL PROTECTED] wrote: I haven't formally checked it, but I would bet that this endofunctor over N, called Sign, is a monad: Just to be picky a functor isn't a monad. A monad is a triple consisting of a functor and 2 natural transformations which make certain diagrams commute. If you are looking for examples, I always think that a partially ordered set is a good because the objects don't have any elements. A functor is then an order preserving map between 2 ordered sets and monad is then a closure (http://en.wikipedia.org/wiki/Closure_operator) - I didn't know this latter fact until I just looked it up. Dominic. ___ 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] Haskell Chess
On Mon, 2007-03-19 at 14:27 +0100, Maxime Henrion wrote: As for the portability of the my graphics code, I can just say it's GTK+, using Glade XML files, Cairo and SVG on top of Cairo. All of this is supposed to work fine on Windows, if that's what you were asking. I'm not sure about OS X but I think it could also work there. My primary target is UNIX. The SVG cairo stuff does build and work on Windows. I didn't include it in the standard build of the installer since it depends on rather more C libs and made the download a bit bigger than I'd have liked for such a small addition. So we could do another build with that in. Deploying Gtk+ apps on windows is pretty easy, I'm going to write a bit about how to it some time, but in the mean time here's one I prepared earlier: http://haskell.org/~duncan/gtk2hs/LSystemSetup.exe Users don't need GHC or Gtk+ installed, you just bundle all the .dlls and the download isn't too big I think (3.5M compressed installer for a 1Mb GHC-built .exe + all the Gtk+ dlls). I've got pre-prepared bundles of gtk+ .dlls that you can use when building an installer (and another bundle incuding the other header files and stuff needed to build Gtk2Hs from source): http://haskell.org/gtk2hs/win32/ Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell and AI
Ok, I've done some more thinking about this. I think the primary difference between the games you cited in your article, and more complex games is that for more complex games, it's easier to think of a strategy as a function of the current board position, rather than the moves leading up to it. For games like Nim, it's not so hard to characterize the moves made thus far, and devise a strategy. Take chess for an example of a more complex game though. Let's just consider a couple of moves from the starting position (I'll assume you know or can work out the meaning of this basic notation). f2-f3, e7-e5, g2-g4. Now black has a mate-in-1 he can play: d8-h4#. This is relatively trivial to see from the given position - yet the 2 main pieces involved in the mate (the black queen and white king) haven't even been moved yet, and it's not at all easy to see just what the given moves have to do with the mate. It's much easier if you take the original position, make the moves, and then create a strategy that is a function of the current position. So, while I'm not necessarily disagreeing with anything you said in your article, I'm just not sure this is a viable way to model game-playing strategies for non-trivial games. I'd definitely like to hear more of your thoughts on this though. Thanks for all your great work! On 3/19/07, Andrew Wagner [EMAIL PROTECTED] wrote: Hi Dan, I just made the connection between you and your blog, by the way - great stuff, keep it up. This particular blog is fascinating, too, but I'm not sure how useful it is to look at more complex 2-player games this way. I'll have to think about it some more On 3/19/07, Dan Piponi [EMAIL PROTECTED] wrote: From: Andrew Wagner [EMAIL PROTECTED] After all, functional programming has long been recognized for being good at AI, yet you rarely hear about it being done in Haskell. A small observation that might or might not be useful for implementing game AIs: 2 player games and their strategies form a monad in a non-trivial way. http://sigfpe.blogspot.com/2006/10/games-strategies-and-self-composition.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] flip fix and iterate (was: Lazy IO and closing of file handles)
Bryan Burgers: On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. I don't know of any tutorials that teach how to use fix, but these are some of the pages that helped me on the way towards understanding what it is: http://en.wikipedia.org/wiki/Fixed_point_combinator http://en.wikipedia.org/wiki/Anonymous_recursion In Haskell, it might help to note the equivalence between a and a', b and b', etc, in the following (given appropriate definitions for p, q, r, s, t, etc): a = fix (\f - if t then f else r) a' = let f = (if t then f else r) in f b = fix (\f x - if t' x then f (s' x) else r' x) p b' = let f x = (if t' x then f (s' x) else r' x) in f p c = fix (\f x y - if t'' x y then uncurry f (s'' x y) else r'' x y) p q c' = let f x y = (if t'' x y then uncurry f (s'' x y) else r'' x y) in f p q etc. The first case is not of much practical use, since each iteration of f must produce the same result, so it must either return immediately (if it doesn't recurse into f) or never (if it does). The other cases can be useful, since the additional arguments can be used by the implementation of f to decide whether or not to recurse. When writing an anonymous function inside an invocation of fix, the main thing to realise is that the first argument of that anonymous function is the anonymous function itself. You can use that argument to make a recursive call to the anonymous function. So you could say it's not really anonymous after all. Of course, you eventually have to return without recursing if you want to avoid an infinite loop. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: flip fix and iterate
Bryan Burgers [EMAIL PROTECTED] wrote in article [EMAIL PROTECTED] in gmane.comp.lang.haskell.cafe: On the topic of 'fix', is there any good tutorial for fix? I searched google, but mostly came up with pages including things like 'bug fix'. It's hard for me to get an intuition about it when 'fix' always stack overflows on me because I don't really know how to use it. Perhaps try: Bruce J. McAdam. 1997. That about wraps it up: Using FIX to handle errors without exceptions, and other programming tricks. Tech. Rep. ECS-LFCS-97-375, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh. http://www.lfcs.informatics.ed.ac.uk/reports/97/ECS-LFCS-97-375/ -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig This is a fairly straightforward coding problem: There aren't many really interesting ways to screw up. -- Leslie Lamport ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Two Other AI Sources
Just in case it helps, I ported the code of Norvigs Paradigms of Artificial Intelligence Programming chapter 8 (integrals and derivates) for a collage course. It passes all the tests proposed by Norvig in his book, includes an expression parser written in Parsec and has a small libreadline interpreter. I as well have a pretty bad written report (done in a hurry before the deadline) but could be useful to understand the differences between the Norvigs implementation and my port. On 3/19/07, Adam Wyner [EMAIL PROTECTED] wrote: For the Haskell and AI work, we ought to consider AI programming books in addition to Russell and Norvig: /Paradigms of AI Programming: Case Studies in Common Lisp/, P. Norvig, 1991. /Prolog Programming for Artificial Intelligence/, I. Bratko, 1990./ Artificial Intelligence Techniques in Prolog/, Y. Shoham, 1994. Perhaps there are newer additions (e.g. Bratko), but the problems and solutions from these languages are presented. We can build on them rather than starting from scratch or even just the theoretical outline of Russell and Norvig. Adam ___ 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
[Haskell-cafe] Re: There can be only one fix? Pondering Bekic's lemma
Nicolas Frisby wrote: My question is: Given products and a fixed point combinator, can any pure expression be transformed into a corresponding expression that has just a single use of fix? Albert Y. C. Lai pointed out model-theoretical and CPU-practical answers. There is also a Haskell-automatic answer. That is, polyvariadic fixpoint, a combinator to obtain a mutually least fixpoint of several terms, is expressible in Haskell itself, via the regular fix: http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic I like its inferred type fix':: [[a-b]-a-b] - [a-b] which is truly the type of the (applicative, or eta-expanded) regular fix with some round parentheses replaced with square ones. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Matrices in Haskell
Ivan Miljenovic: As such, I'd like to know if there's any way of storing a an n-by-n matrix such that the algorithm/function to get either the rows or the columns is less than O(n^2) like transposition is. I did try using an Array, but my (admittedly hurried and naive) usage of them took longer than a list of lists, was more difficult to manipulate, and wasn't required separate inverse functions to row and cols. Also, since I need to look all throughout the list of values, it's still O(n^2), but this time for both rows and columns. I'm not sure I see the problem, since any operation that touches all the elements of a n-by-n matrix will be at least O(n^2). For such an operation, a transposition should just add a constant factor. When you tried using Arrays, I presume you used an array indexed by a pair (i,j), and just reversed the order of the index pair to switch from row-wise to column-wise access? It's hard to see how that would slow you down. Perhaps the slowdown was caused by excessive array copying? Immutable arrays can be efficient for algorithms that write a whole array at once, but usually not for algorithms that modify one element at a time. I think you'll need to show specific functions that are performing below expectation before the list will be able to help. For problems like latin squares and sudoku, also try thinking outside the matrix. Do you really need to structure the problem in terms of rows and columns? What about a set of mutually-intersecting sets of cells? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
