Re: [Haskell-cafe] library sort
On 2/16/06, Jared Updike <[EMAIL PROTECTED]> wrote: > If you need an easier way to search the Haskell APIs, use Hoogle: Hoogle is very nice. Thanks to everyone who answered my question about finding a sort library function. -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] library sort
Is there a sort function in the libraries that come with GHC (6.4)? My search at http://www.haskell.org/ghc/docs/latest/html/libraries/index.html has failed, but I can't believe there is none. -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Problems with square root...
On 12/21/05, Daniel Carrera <[EMAIL PROTECTED]> wrote: > > round sqrt(2) > I don't understand why it dosn't work without brackets. Function application is left associative in Haskell. -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell-style proof tools?
On 9/21/05, Robin Green <[EMAIL PROTECTED]> wrote: > Does anyone know of a prover / proof assistant / proof verifier which uses a > vaguely Haskell-like syntax? That is to say, it allows you to express > theorems in Haskell-style syntax, print proof steps in Haskell-style syntax, > etc. Skimming through the Haskell report reveals links that seem promising: http://www.cs.chalmers.se/~catarina/agda/ http://www.haskell.org/yarrow/ And maybe: http://www.ittc.ku.edu/~wardj/prufrock/ -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Coin changing algorithm
On 7/13/05, Dinh Tien Tuan Anh <[EMAIL PROTECTED]> wrote: > i guess i have to learn Monads then, ^_^ That's probably a good idea. But what about this problem made you think "monads"? Caching? The imperative solution you mentioned? -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Coin changing algorithm
On 7/13/05, ChrisK <[EMAIL PROTECTED]> wrote: > Sort the list of integers, highest at the front of the list. > (And perhaps remove duplicates with nub) The first time I wrote in the comments that 'partition' takes a "decreasing list of integers..." and then I decided to drop "decreasing". Weakest precondition :) > When you pop the first element you can already compute the range of > quantity you will need, Is that really faster? I wouldn't be sure without profiling.. -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Coin changing algorithm
On 7/13/05, Dinh Tien Tuan Anh <[EMAIL PROTECTED]> wrote: > Any idea ? This is the first thing I wrote when i read your problem: === begin integer_partition.lhs === This is a solution to a question asked on Haskell cafe. The problem looks like a classical one. You are given a list of positive integers and integers m and n. You are to find all multisets with at most k elements from the given list that sum up to m. The idea is to write a recursive function that divides the problem into finding multisets with various maximal elements. > partition :: [Int] -> Int -> Int -> [[Int]] The base case with exactly one solution > partition _ m _ | m == 0 = [[]] The base cases with no solution > partition [] _ _ = [] > partition _ m _ | m < 0 = [] > partition _ _ k | k <= 0 = [] Now we are prepared to attack the general case: > partition (x:xs) m k = > (prefix x (partition (x:xs) (m-x) (pred k))) > ++ > (partition xs m k) The prefix function simply prepends a value to every list. > prefix :: Int -> [[Int]] -> [[Int]] > prefix x = map (\xs -> x:xs) Now, how to memoize this one? As is it is a SLOW solution. === end integer_partition.lhs === -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiling an extremely large Haskell file (in GHC)
On 6/29/05, Duncan Coutts <[EMAIL PROTECTED]> wrote: > Indeed I understand from a colleague who implemented an all-pairs > shortest paths algorithm in Haskell over the weekend for a map of the > Hyde Park area of Chicago (no real reason, really!), that it takes about > 0.1 seconds to execute (if you compile with -O), which is well within > the 5 second limit... Well, that is about two times slower than c++ code :p ... I mean: it's way faster that what I would have expected :) Anyway, I am interested in how DP-like algorithms are implemented in Haskell (with the same complexities), not in this particular problem. A week ago I tried LCS, now the ICFP contest fed me with another algorithm that isn't trivial to implement in this language. For ICFPC you could use some other solution than Floyd-Warshall but, again, I am asking about _this_ particular algorithm. > I wonder why everyone is so interested in the distances between > intersections in the Hyde Park area of Chicago all of a sudden... You are right: I'll ask again in 2 weeks. So please don't answer to this post :) -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compiling an extremely large Haskell file (in GHC)
On 6/27/05, Arjun Guha <[EMAIL PROTECTED]> wrote: > It's the all-pairs > shortest paths data for a map of the Hyde Park area of Chicago (no real > reason, really). I wonder: is there really no way to do Floyd-Warshall in Haskell? -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (small) code review request
On 6/16/05, Lennart Augustsson <[EMAIL PROTECTED]> wrote: > fib n = f n 1 1 >where f 0 _ b = b > f n a b = f (n-1) (a+b) a Indeed. I should have seen this. It's a pretty standard trick for making a function tail recursive. > List based solutions should also work if garbage collection > is done right, e.g., > fib n = fs !! n >where fs = 1 : 1 : zipWith (+) fs (tail fs) So you mean my solution of the LCS problem should work in O(n) space "if garbage collection is done right"? What exactly does this condition mean in practice? -- regards, radu http://rgrig.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (small) code review request
The programming language I know best is C++. Wait, don't close the message.
I also know OCaml and a couple of days ago I read "A Gentle
Introduction to Haskell". In order to practice what I've learned a bit
above "hello world" programs I chose to solve some easy tasks from
SPOJ. They have automatic testing so I know if I got it right or not
and I can also look at submission statistics (number and accuracy) to
choose easy problems. Aside from "easiness" I've chosen at random
these:
https://spoj.sphere.pl/problems/ADDREV/
https://spoj.sphere.pl/problems/CRSCNTRY/
So these are my first two Haskell "programs" and I'd appreciate any
comments you might have, especially better ways of solving the
problems.
The first one asks you to print rev(rev a + rev b) for two numbers a
and b where rev is a function that transforms an integer into an
integer you get by reversing the digits.
--- BEGIN addrev.hs ---
rev :: Int -> Int
rev = read . reverse . show
solve :: Int -> IO ()
solve 0 = do return ()
solve n = do
line <- getLine
let
a:b:_ = words line
an = read a
bn = read b in
(putStrLn . show . rev) (rev an + rev bn)
solve (n-1)
main = do
hSetBuffering stdin LineBuffering
line <- getLine
solve (read line)
--- END addrev.hs ---
The second problem happens to be the Longest Common Subsequence
problem, which is a classical DP problem. After searching a bit how to
do memoisation/dp in Haskell I've found two resources:
http://www.haskell.org/hawiki/MemoisingCafs
http://portal.acm.org/citation.cfm?id=871896&coll=Portal&dl=ACM&CFID=46143395&CFTOKEN=4814124
I chose to try the approach in the Bird&Hinze article. The result is
my second Haskell program:
--- BEGIN crscntry.lhs ---
One of the problems at SPOJ, namely CRSCNTRY, asks you to implement
the classical (DP) algorithm for finding the length of the longest
common subsequence. The reccurence relation is:
lcs [] _ = 0
lcs _ [] = 0
lcs (x:xs) (y:ys) =
| x == y= 1 + lcs xs ys
| otherwise = lcs (x:xs) ys `max` lcs xs (y:ys)
There are of course only mn distinct calls to lcs, where
m = 1 + length xs, n = 1 + length ys. I will try here a memoisation
approach about which I have read in "Trouble shared is trouble halved",
by Bird and Hinze. The basic idea is to explicitly construct the
call tree and store in it the result of computing the function.
First, note that the reccurence relation above makes either one or
two calls. I think we can get by with a binary tree that has this
invariant:
left . right n = right . left n
Let's define the tree.
> data Tree a = Empty | Node { left :: Tree a, info :: a, right :: Tree a }
> leaf :: a -> Tree a
> leaf x = Node Empty x Empty
Now imagine the tree nodes put into a matrix
l l
x <--- x <--- x
^ ^ ^
|r l |r l |r
x <--- x <--- x
We use two memoisation functions. One of them constructs all the rows
above (memo_lcs), while the other reuses the nodes above and constructs
only one row to the left (memo_lcs'). We also pass around the lists so
that we can constructs nodes correctly.
> memo_lcs :: Eq a => [a] -> [a] -> Tree Integer
> memo_lcs [] _ = Empty
> memo_lcs _ [] = Empty
> memo_lcs (x:xs) (y:ys) =
> node x y (memo_lcs' t xs (y:ys)) t
> where t = memo_lcs (x:xs) ys
> memo_lcs' :: Eq a => Tree Integer -> [a] -> [a] -> Tree Integer
> memo_lcs' _ [] _ = Empty
> memo_lcs' _ _ [] = Empty
> memo_lcs' z (x:xs) (y:ys) =
> node x y (memo_lcs' l xs (y:ys)) l
> where l = tree_left z
Both of these functions use a smart constructor. It takes the left
and right branches and constructs a new node while also computing the
correct value the function must have.
> node :: Eq a => a -> a -> Tree Integer -> Tree Integer -> Tree Integer
> node x y l r
> | x == y= Node l (1 + (value . tree_left) r) r
> | otherwise = Node l (value l `max` value r) r
The inspection of the value returns 0 for empty nodes.
> value :: Tree Integer -> Integer
> value Empty = 0
> value (Node _ r _) = r
You might be wondering by now what is the function tree_left.
> tree_left :: Tree a -> Tree a
> tree_left Empty = Empty
> tree_left (Node l _ _) = l
(I wonder if all this would be simpler if I'd use a border of 0-valued
leafs instead of the functions tree_left and value. I'll try soon.)
Now the definition of lcs is simple.
> lcs :: Eq a => [a] -> [a] -> Integer
> lcs x y = value (memo_lcs x y)
This is the basic solution of the problem CRSCNTRY. A testcase is just
a bit more complicated.
> testcase:: [[Integer]] -> Integer
> testcase (x:xs) = foldl max 0 (map (lcs x) xs)
In order to finish we just need to take care of the IO.
> myReadList :: String -> [Integer]
> myReadList s =
> let (a, t) = head (lex s) in
> case read a of
> 0 -> []
> n -> n : (myReadList t)
> readTest :: IO [[Integer]]
> readTest = do
> line <- getLine
> case myReadList line of
> [] -> do return []
> lst -> do
> rest <- re
Re: [Haskell-cafe] I love type declarations. :-)
On 5/6/05, Daniel Carrera <[EMAIL PROTECTED]> wrote:
> function :: Int -> Int -> [Int]
> Before, when writing imperative code, I would add a comment for each
> function describing its input and output. Now type declarations provide
What do you mean? In C++ one would write:
vector function(int a, int b) { ... }
Type annotations are independent of functional/imperative style.
(Although C++, the most used imperative language requires type
annotations).
--
regards,
radu
http://rgrig.blogspot.com/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ghc install
Hi, I try to install ghc on 6.2 on a gentoo linux distribution (from sources). It fails with --- /usr/bin/ar: creating libHSbase.a xargs: /usr/bin/ar: terminated by signal 15 --- It looks like it's a lack of resources. The computer is a Celeron 1.3GHz with 160MB RAM & 400MB swap. Isn't that enough to compile ghc? -- regards, radu http://rgrig.idilis.ro/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
