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
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
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
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
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
#1236: System.Mem.Weak breaks referential transparency
-+--
Reporter: [EMAIL PROTECTED] | Owner:
Type: bug | Status: new
Priority: normal| Milestone:
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
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
| 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
|
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
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
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
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.
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
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
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
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
[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
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
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
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
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
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
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
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
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 -
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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)
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]
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
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
-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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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.
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.
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
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
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
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
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
81 matches
Mail list logo