Re: [Haskell-cafe] Why Perl is more learnable than Haskell

[Valery V. Vorotyntsev]

Dave Feustel <[EMAIL PROTECTED]> writes:

> A serious omission in Haskell tutorials is a collection of examples of how to 
> write Haskell solutions for problems that would use arrays in any imperative 
> language.
> I see that arrays can be defined in Haskell, but I don't see their use as
> computationally efficient in Haskell.

"By replacing the string type with our ByteString representation,
Haskell is able to approach the speed of C, while still retaining the
elegance of the idiomatic implementation. With stream fusion enabled,
it actually beats the original C program. Only by sacrificing clarity
and explicitly manipulating mutable blocks is the C program able to
outperform Haskell."
- http://www.cse.unsw.edu.au/~dons/papers/CSL06.html

"The ability to fuse all common list functions allows the programmer
to write in an elegant declarative style, and still produce excellent
low level code. We can finally write the code we *want* to be able to
write without sacrificing performance!"
- http://www.cse.unsw.edu.au/~dons/papers/CLS07.html

Don't give up.
;-)

-vvv
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Nicolas Frisby]

[sorry for the double, ajb]

Since there seemed to be a disconnect between the expectation and
the previous answers, I thought an alternative suggestion might help
out. This sort of thing (haha) usually isn't my cup o' tea, so please
point out any blunders.

RM, is this more like what you had in mind? It leans more towards an
iterative approach. If so, I encourage you to compare this to the
other solutions and try understand how those solutions rely upon
laziness. Stefan and Andrew, feel free to point out the drawbacks to
this approach that I'm probably overlooking.


kminima n l = map fst (foldr insert' (List.sort pre) suf)
   where (pre, suf) = (splitAt n . zip [0..]) l

-- I think this insertion sort could be
-- O(log k) with a better data structure.
insert' x [] = []
insert' x (y : ys) | snd x < snd y = x : y : dropLast ys'
  | otherwise = y : insert' x ys
   where dropLast ys = take (length ys - 1) ys

We grab the first k elements and sort them, this list is our first
approximation to the k-minima. We then process the rest of the list,
checking if the current element is smaller than any of the minima of
the current approximation. If the current element is smaller, we
improve the current approximation by inserting the new element and
dropping the biggest (i.e. last) minimum from the minima accumulator.

The worst behavior is: sort(k) + (n-k) * k comparisons. This could be
improved (to: sort(k) + (n-k) * log k comparisons, I think) with a
better data structure for the minima approximation.

On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:

G'day all.

Quoting raghu vardhan <[EMAIL PROTECTED]>:

> So, any algorithm that sorts is no good (think of n as huge, and k small).

The essence of all the answers that you've received is that it doesn't
matter if k is small, sorting is still the most elegant answer in Haskell.

The reason is that in Haskell, a function which sort function will produce the
sorted
list lazily.  If you don't demand the while list, you don't perform
the whole sort.

Some algorithms are better than others for minimising the amount of
work if not all of the list is demanded, but ideally, producing the
first k elements will take O(n log k + k) time.

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] c2hs on mac

[Duncan Coutts]

On Thu, 2007-04-12 at 16:02 +1000, Ruben Zilibowitz wrote:

> I can't even check out the darcs version from the repository because  
> that gives me an error (on applying patch 107/256 from memory). So I  
> am using the tarball for c2hs-0.14.5. Here is the problem:

Ah, the problem with case sensitive file names. I've made a new
checkpoint in the darcs repo so if you use darcs get --partial then you
can avoid having to download and apply the problematic patch. So give
this another go:

darcs get --partial http://darcs.haskell.org/c2hs/

> ./Setup.hs:11:57:
>  Couldn't match expected type  
[..]

This was due to changes in the cabal api. In the darcs version of c2hs
I've removed all the custom code from Setup.hs and found better ways of
doing it. We need a new c2hs release, but I'm still somewhat in the
middle of improving the parser and I'd like to do at least a bit of
testing before making a release :-)

> I have ghc 6.6 installed. I also have ghc 6.7.x installed in a  
> different location. I would like to be able to use c2hs with ghc  
> 6.7.x if possible.

Try the darcs version.

uncan

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Why Perl is more learnable than Haskell

[Udo Stenzel]

kynn wrote:
> (I don't need elegant
> factorial or Fibonacci functions in my everyday work.)

I think you do.  Most of your utility programs probably fit into the
simple frame of

main = interact $ unlines . map f . lines

for suitable f.  Of course, f is hardly ever the factorial function, but
it is a function.  My guess is, you think you "just wanted a loop" when
in reality you need to lift a function to work over a list.


> Or I can always wait until I retire; then I'll probably have a sufficiently
> long stretch of free time in my hands

You may need patience, too.


-Udo


signature.asc
Description: Digital signature
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] c2hs on mac

[Ruben Zilibowitz]

Ok I managed to check out a version from darcs. Now this is happening:
./Setup.hs build
Preprocessing executables for c2hs-0.14.6...
Setup.hs: c2hs/c/CLexer.x: no alex preprocessor available

The installation instructions don't mention that I need the alex  
package. I guess I can just install it and try again. Are there any  
other prerequisites though?


Ruben

On 12/04/2007, at 5:30 PM, Duncan Coutts wrote:


On Thu, 2007-04-12 at 16:02 +1000, Ruben Zilibowitz wrote:


I can't even check out the darcs version from the repository because
that gives me an error (on applying patch 107/256 from memory). So I
am using the tarball for c2hs-0.14.5. Here is the problem:


Ah, the problem with case sensitive file names. I've made a new
checkpoint in the darcs repo so if you use darcs get --partial then  
you

can avoid having to download and apply the problematic patch. So give
this another go:

darcs get --partial http://darcs.haskell.org/c2hs/


./Setup.hs:11:57:
 Couldn't match expected type

[..]

This was due to changes in the cabal api. In the darcs version of c2hs
I've removed all the custom code from Setup.hs and found better  
ways of

doing it. We need a new c2hs release, but I'm still somewhat in the
middle of improving the parser and I'd like to do at least a bit of
testing before making a release :-)


I have ghc 6.6 installed. I also have ghc 6.7.x installed in a
different location. I would like to be able to use c2hs with ghc
6.7.x if possible.


Try the darcs version.

uncan



___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: k-minima in Haskell

[apfelmus]

raghu vardhan <[EMAIL PROTECTED]>:
> So, any algorithm that sorts is no good (think of n as huge, and k small).

With lazy evaluation, it is!

  http://article.gmane.org/gmane.comp.lang.haskell.general/15010


[EMAIL PROTECTED] wrote:
> The essence of all the answers that you've received is that it doesn't
> matter if k is small, sorting is still the most elegant answer in Haskell.

(It's not only most elegant, it can even be put to work.)

> The reason is that in Haskell, a function which sort function will produce the
> sorted list lazily. If you don't demand the while list, you don't perform
> the whole sort.
> 
> Some algorithms are better than others for minimising the amount of
> work if not all of the list is demanded, but ideally, producing the
> first k elements will take O(n log k + k) time.

You mean O(k * log n + n) of course.

Regards,
apfelmus

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] c2hs on mac

[Duncan Coutts]

On Thu, 2007-04-12 at 18:55 +1000, Ruben Zilibowitz wrote:
> Ok I managed to check out a version from darcs. Now this is happening:
> ./Setup.hs build
> Preprocessing executables for c2hs-0.14.6...
> Setup.hs: c2hs/c/CLexer.x: no alex preprocessor available
> 
> The installation instructions don't mention that I need the alex  
> package.

The tarball versions come with pre-generated lexer and parser files but
the darcs version does not.

> I guess I can just install it and try again. Are there any other
> prerequisites though?

Yes, you also need 'happy' the parser generator.
http://haskell.org/happy/

Duncan

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Translating perl -> haskell, string "fill ins" with an error on invalid input seems awfully complex. Is there a way to simplify?

[Thomas Hartman]

I was translating some perl code to haskell as a learning exercise and
wound up with the following. (below) Simple code that accepts some
string arguments, and prints a string -- so, of type String -> String
-> String -> String -> IO ().

I like to be concise, but I get the feeling something went awry.  What
seems to be costing me the most is checking whether the various
arguments are legitimate, and printing a helpful error message if not.

I was able to achieve this by using Maybe and error on failed pattern
match, but as said, seems kind of overly complicated.

Is there a simpler way to do the following, eg for function

 gen_gnuplot_financial_script :: String -> String -> String -> String -> IO ()

?

By the way this is being used in

http://code.google.com/p/gnuplotwebinterface/

**

module Common where

gnuplot_png_settings = "set terminal png transparent nocrop enhanced
size 600,400\n" ++
  "set pm3d implicit at s"

gnuplot_math_settings =  gnuplot_png_settings ++ "\n" ++
"set border 4095 \n\
\  set xlabel \"x\" \n\
\  set ylabel \"y\""

gnuplot_timeseries_settings = gnuplot_png_settings ++ "\n" ++
 "set xdata time   # The x axis
data is time \n" ++
 "set timefmt \"%d-%b-%y\" # The dates in
the file look like 10-Jun-04 \n" ++
 "set format x \"%b %d\"   #On the
x-axis, we want tics like Jun 10"


gen_gnuplot_math_script :: String -> String -> IO ()
gen_gnuplot_math_script style function = let maybePlotCmd = lookup
style style_to_plotcmd
style_to_plotcmd =
[("math-2d","plot"),("math-3d","splot")]
  in case maybePlotCmd of
   Just plotcmd ->
putStrLn $ gnuplot_math_settings ++ "\n" ++ plotcmd ++ " "  ++
function
   _-> error
$ "bad style: " ++ style

gen_gnuplot_financial_script :: String -> String -> String -> String -> IO ()
gen_gnuplot_financial_script company displaymode startDate endDate
   = let maybeCompanyFile = lookup company company_to_companyfile
 maybeModeString  = lookup displaymode displaymode_to_modestring
 maybeTitleEnd= lookup displaymode displaymode_to_titleend
 company_to_companyfile =
[("ibm","data/ibm.dat"),("cisco","data/cisco.dat")]
 displaymode_to_modestring = [("points", "using 1:2 with linespoints"),
  ("candles","using
1:($2+$3+$4+$5)/4:4:3 with yerrorbars")]
 displaymode_to_titleend = [("points","daily
prices"),("candles","opening prices")]
   in case ( maybeCompanyFile,
 maybeModeString,
 maybeTitleEnd ) of
   ( Just companyfile,
 Just modestring,
 Just titleEnd) -> putStrLn $
gnuplot_timeseries_settings ++ "\n" ++
 "plot [\"" ++ startDate ++ "\":\"" ++
endDate ++ "\"]"
 ++ " '" ++ companyfile ++ "'"
 ++ modestring
 ++ " title \"" ++ company ++ " " ++
titleEnd ++ "\""
   _ -> error $ "bad lookup. " ++ company ++ " ->
company file: " ++ ( show maybeCompanyFile ) ++ "\n" ++
"" ++ displaymode ++ " ->
displaymode: "  ++ ( show maybeModeString ) ++ "\n" ++
"" ++ displaymode ++ " ->
titleEnd: " ++ ( show maybeTitleEnd)
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: hackage.haskell.org

[Simon Marlow]

Neil Mitchell wrote:

> Let's hold off on this for now.  I don't think Haddock warrants a full
> Trac of
> its own just yet, the overheads of managing a Trac are pretty high
> compared to
> editing the text file called "TODO" in the root of the Haddock 
source tree

> :-)

What do you think of the Google bug tracker? Neil and I created a project
for Haddock at http://code.google.com/p/haddock/


For reference, it took well under a minute for me to create a new
Google Code project, and is unlikely to need maintenance ever.

Google rules!


I'm thinking of the overheads of using a web app to manage a bug database as 
opposed to a text file + darcs + email.  Google code is certainly good, but it 
isn't going to beat the low-tech tools in terms of simplicity and speed.  What's 
more, we'll have to populate it with all the existing known bugs, or keep bugs 
in two places.  And can you extract the metadata from google code when you want 
to move to Trac or something else?


I'm mainly worried that I'll have yet another place to go looking for bugs.

David - if you want to set up a Google bug tracker for haddock.ghc then by all 
means go ahead, but my vote would be to keep it simple, at least until we really 
need the extra functionality.


Cheers,
Simon

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Type checking with Haskell

[Joel Reymont]

Folks,

The ghc/compiler/typecheck directory holds a rather large body of  
code and quick browsing through did not produce any insight.


How do you implement type checking in haskell?

Assume I have an Expr type with a constructor per type and functions  
can take lists of expressions. Do I create a function taking an Expr,  
pattern-matching on appropriate constructor and returning True on a  
match and False otherwise?


Thanks, Joel

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] c2hs on mac

[Ruben Zilibowitz]

Ok, thanks. I finally managed to build it.

Ruben

On 12/04/2007, at 8:30 PM, Duncan Coutts wrote:


On Thu, 2007-04-12 at 18:55 +1000, Ruben Zilibowitz wrote:
Ok I managed to check out a version from darcs. Now this is  
happening:

./Setup.hs build
Preprocessing executables for c2hs-0.14.6...
Setup.hs: c2hs/c/CLexer.x: no alex preprocessor available

The installation instructions don't mention that I need the alex
package.


The tarball versions come with pre-generated lexer and parser files  
but

the darcs version does not.


I guess I can just install it and try again. Are there any other
prerequisites though?


Yes, you also need 'happy' the parser generator.
http://haskell.org/happy/

Duncan



___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Stefan Holdermans]

Joel,


How do you implement type checking in haskell?


You might want to check out "Typing Haskell in Haskell" [1] by Mark  
P. Jones.


Cheers,

  Stefan

[1] Jones, Mark P. Typing Haskell in Haskell. In Erik Meijer, editor,  
Proceedings of the 1999 Haskell Workshop, Friday October 9th, 1999,  
Paris, France. 1999. The proceedings of
the workshop have been published as a technical report (UU- 
CS-1999-28) at Utrecht University. http://www.cs.uu.nl/research/ 
techreps/UU-CS-1999-28.html

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Joel Reymont]

On Apr 12, 2007, at 1:07 PM, Stefan Holdermans wrote:

You might want to check out "Typing Haskell in Haskell" [1] by Mark  
P. Jones.


Must be _the_ paper as Don suggested it as well.

I also looked at my copy of Andrew Appel's compilers in ML book and  
realized that I should be going about it differently than I thought,  
i.e. figuring out and returning the type of an expression rather than  
matching constructors. Oh, well.


Thanks, Joel

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Typing non-Haskell in Haskell

[Joel Reymont]

I feel I should set aside a Friday of every week just to read the  
Haskell papers :-).


After skimming through "Typing Haskell in Haskell" I have a couple of  
questions...


Are type constructors (TyCon) applicable to Haskell only? Mine is a  
Pascal-like language.


How would I type Pascal functions as opposed to Haskell ones? It  
seems that the approach is the same and I still need TyCon "(->)".


Thanks, Joel

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Typing non-Haskell in Haskell

[Bjorn Bringert]

On Apr 12, 2007, at 14:37 , Joel Reymont wrote:

I feel I should set aside a Friday of every week just to read the  
Haskell papers :-).


After skimming through "Typing Haskell in Haskell" I have a couple  
of questions...


Are type constructors (TyCon) applicable to Haskell only? Mine is a  
Pascal-like language.


How would I type Pascal functions as opposed to Haskell ones? It  
seems that the approach is the same and I still need TyCon "(->)".


Thanks, Joel



Here are some lecture notes about implementing type checking for an  
imperative language from a programming languages course:


http://www.cs.chalmers.se/Cs/Grundutb/Kurser/progs/current/lectures/ 
proglang-08.html


/Björn___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

RE: [Haskell-cafe] Type checking with Haskell

[Bernie Pope]

Hi Joel,

You may like to check out my mini-interpreter called (cheekily) baskell:

   http://www.cs.mu.oz.au/~bjpop/code.html

It has type inference, and it is pretty straightforward. I wrote it for
teaching purposes.

First, I pass over the AST and generate a set of typing constraints. They
are just equality constraints. Then I solve the constraints. Couldn't be
much simpler than that. Mind you, the input language is pretty minimal (no
type classes etcetera). 

Cheers,
Bernie.

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:haskell-cafe-
> [EMAIL PROTECTED] On Behalf Of Joel Reymont
> Sent: 12 April 2007 13:04
> To: Haskell Cafe
> Subject: [Haskell-cafe] Type checking with Haskell
> 
> Folks,
> 
> The ghc/compiler/typecheck directory holds a rather large body of
> code and quick browsing through did not produce any insight.
> 
> How do you implement type checking in haskell?
> 
> Assume I have an Expr type with a constructor per type and functions
> can take lists of expressions. Do I create a function taking an Expr,
> pattern-matching on appropriate constructor and returning True on a
> match and False otherwise?
> 
>   Thanks, Joel
> 
> --
> http://wagerlabs.com/
> 
> 
> 
> 
> 
> ___
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Compiling GHC

[Andrew Appleyard]

On 11/04/2007, at 7:52 pm, Chris Witte wrote:

I made this change but I still get the error
unknown symbol `_gettimeofday'
I'm using mingw 5.1.3 which as far as i can tell should use the  
3.11 runtime.


Ensure that HAVE_GETTIMEOFDAY is defined in mk/config.h.

Also, I discovered that changes to Linker.c don't make it into  
ghc.exe if you just do a 'make' in the base directory.  You need to  
make the RTS, then link ghc with the new RTS.  The following commands  
work for me (more typing, but a lot faster than making clean):


  make -C rts
  rm compiler/stage2/ghc.exe
  make -C compiler stage=2
  make install

Hope that helps.

Regards,
Andrew.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Why Perl is more learnable than Haskell

[kynn]

Hi.  I can't find that post.  Could you point it to me please?

Thanks!

kj


riccardo cagnasso wrote:
> 
> The post on dons' blog about the cpu scaler is a great example on how
> haskell can easily used in the day-to-day hacking!
> 
> 
> 2007/4/11, brad clawsie <[EMAIL PROTECTED]>:
>>
>> i find that don's "haskell hacking blog" has been written with the daily
>> hacker in mind:
>>
>> http://cgi.cse.unsw.edu.au/~dons/blog
>> ___
>> Haskell-Cafe mailing list
>> [EMAIL PROTECTED]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
> 
> 
> 
> -- 
> I invented the term Object-Oriented, and I can tell you I did not have C++
> in mind. (Alan Kay)
> 
> ___
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

-- 
View this message in context: 
http://www.nabble.com/Why-Perl-is-more-learnable-than-Haskell-tf3559193.html#a9959852
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Why Perl is more learnable than Haskell

[Alex Queiroz]

Hallo,

On 4/12/07, kynn <[EMAIL PROTECTED]> wrote:


Hi.  I can't find that post.  Could you point it to me please?



It's in here:
http://cgi.cse.unsw.edu.au/~dons/blog/2007/03/10#programmable-semicolons

--
-alex
http://www.ventonegro.org/
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Stefan O'Rear]

On Thu, Apr 12, 2007 at 01:04:13PM +0100, Joel Reymont wrote:
> Folks,
> 
> The ghc/compiler/typecheck directory holds a rather large body of  
> code and quick browsing through did not produce any insight.
> 
> How do you implement type checking in haskell?
> 
> Assume I have an Expr type with a constructor per type and functions  
> can take lists of expressions. Do I create a function taking an Expr,  
> pattern-matching on appropriate constructor and returning True on a  
> match and False otherwise?

The Glasgow Haskell typechecker is big not because type checking is
hard, but because GHC Haskell is a very big language.  Also, GHC runs
typechecking *before* desugaring, apparently thinking error messages
are more important than programmer sanity :)

A typechecker for a simpler language can be implemented quite easily:

--- Simply typed lambda calculus

data Typ = Int | Real | Bool | Fn Typ Typ
data Exp = Lam Typ Exp | Var Int | App Exp Exp

typeCheck' :: [Typ] -> Exp -> Maybe Typ
typeCheck' cx (Lam ty bd) = fmap (Fn ty) (typeCheck' (ty:cx) bd)
typeCheck' cx (Var i) = Just (cx !! i)
typeCheck' cx (App fn vl) = do Fn at rt <- typeCheck' cx fn
   pt   <- typeCheck' cx vl
   guard (at == pt)
   return rt

Your problem, as I understand it, is even simpler than most since
there are no higher order functions and no arguments.

---

data Typ = Real | Int | Bool | String

tc2 a b ta tb tr | typeCheck a == ta && typeCheck b == tb = Just tr
 | otherwise  = Nothing

typeCheck :: Exp -> Maybe Typ
typeCheck (IAdd a b) = tc2 a b Int Int Int
...

(That said, it would probably be better to fuse parsing and type
checking in this case so that you do not need to track source
positions.)

Stefan
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Dino Morelli]

On Thu, 12 Apr 2007, raghu vardhan wrote:



What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least k
elements in the list. The code should be elegant and also, more importantly, 
must not make more than the minimum O(k*length(list)) number of operations.

R M




I don't know about performance, but trying this problem I was struck
again by the gorgeous, terse code that can be created:


import Data.List
import Data.Ord

kminima :: (Enum a, Num a, Ord b) => Int -> [b] -> [a]
kminima k lst = take k $ map fst $ sortBy (comparing snd) $ zip [0 ..] lst


commented:

   kminima k lst =
  take k -- We want k items off the front
  $ map fst  -- Just the list of indices
  $ sortBy (comparing snd)   -- Sort the pairs by their snd
  $ zip [0 ..] lst   -- Preserve indices in tuples


Prelude> :l kminima.hs
[1 of 1] Compiling Main ( kminima.lhs, interpreted )
Ok, modules loaded: Main.
*Main> kminima 3 [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36]
[14,3,4]
*Main> kminima 4 [10,9,8,7,6,5,4,3,2,1]
[9,8,7,6]


--
 .~.Dino Morelli
 /V\email: [EMAIL PROTECTED]
/( )\   irc: dino-
^^-^^   preferred distro: Debian GNU/Linux  http://www.debian.org
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Joel Reymont]

Thanks Stefan!

On Apr 12, 2007, at 3:00 PM, Stefan O'Rear wrote:


Your problem, as I understand it, is even simpler than most since
there are no higher order functions and no arguments.


I do have functions and arguments but I don't have HOF.


(That said, it would probably be better to fuse parsing and type
checking in this case so that you do not need to track source
positions.)


I'm not sure how to do this, quite honestly. The language is  
dynamically typed so I have to infer variable types from their usage,  
function return types from what is assigned to the function name  
(last assignment in program, Fun = xxx). I also have to infer if  
variables are of a series type by checking if any references are made  
to the previous values of those variables.


I don't think it's possible to fuse type checking with parsing here.

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Kurt Hutchinson]

On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:

To get the indices, use the Schwartzian transform:

sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
sortWith f = mergeRuns . runs
  where
runs = map (:[])

mergeRuns [] = []
mergeRuns [xs] = xs
mergeRuns xss = mergeRuns (mergeRun xss)

mergeRun (xs1:xs2:xss) = mergeOne xs1 xs2 : mergeRun xss
mergeRun xss = xss

mergeOne [] ys = ys
mergeOne xs [] = xs
mergeOne xs'@(x:xs) ys':(y:ys)
= case compare (f x) (f y) of
LT -> x : mergeOne xs ys'
GT -> y : mergeOne xs' ys
EQ -> x : y : mergeOne xs ys

getKMinima :: (Ord a) => [a] -> [Int]
getKMinima k = map fst . take k . sortWith snd . zip [0..]


For my own edification, what is the benefit of this sortWith over sortBy?

f `on` g = \ x y -> f ( g x ) ( g y )
kminima k = map fst . take k . sortBy ( compare `on` snd ) . zip [0..]
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Joel Reymont]

On Apr 12, 2007, at 3:00 PM, Stefan O'Rear wrote:

Also, GHC runs typechecking *before* desugaring, apparently  
thinking error messages

are more important than programmer sanity :)


What would be the benefit of running type checking after desugaring?

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Vincent Kraeutler]

Kurt Hutchinson wrote:
> On 4/12/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>> To get the indices, use the Schwartzian transform:
>>
>> sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
>> sortWith f = mergeRuns . runs
>>   where
>> runs = map (:[])
>>
>> mergeRuns [] = []
>> mergeRuns [xs] = xs
>> mergeRuns xss = mergeRuns (mergeRun xss)
>>
>> mergeRun (xs1:xs2:xss) = mergeOne xs1 xs2 : mergeRun xss
>> mergeRun xss = xss
>>
>> mergeOne [] ys = ys
>> mergeOne xs [] = xs
>> mergeOne xs'@(x:xs) ys':(y:ys)
>> = case compare (f x) (f y) of
>> LT -> x : mergeOne xs ys'
>> GT -> y : mergeOne xs' ys
>> EQ -> x : y : mergeOne xs ys
>>
>> getKMinima :: (Ord a) => [a] -> [Int]
>> getKMinima k = map fst . take k . sortWith snd . zip [0..]
>
> For my own edification, what is the benefit of this sortWith over sortBy?
>
> f `on` g = \ x y -> f ( g x ) ( g y )
> kminima k = map fst . take k . sortBy ( compare `on` snd ) . zip [0..]


possibly related (newbie question):

pairs are instances of Ord, why not directly sort those (implying the
item to be sorted is fst):

> kminima k = \list -> map snd $ take k $ sort $ zip list [0..]





signature.asc
Description: OpenPGP digital signature
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Bas van Dijk]

On 4/12/07, Joel Reymont <[EMAIL PROTECTED]> wrote:

What would be the benefit of running type checking after desugaring?


After desugaring, the program is written in a much more simple
language (GHC Core). Type checking a desugared program is much easier
because the type checker has to deal with much less language
constructs than in the original program.

The disadvantage is that after desugaring a lot of the original
program is lost so that the type checker can't give an error message
that exactly describes the location and reason of the error.

Bas van Dijk
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Translating perl -> haskell, string "fill ins" with an error on invalid input seems awfully complex. Is there a way to simplify?

[Dan Mead]

I believe there is a library which lets you do do perl style REGEX matching

maybe you should check that out

On 4/12/07, Thomas Hartman <[EMAIL PROTECTED]> wrote:


I was translating some perl code to haskell as a learning exercise and
wound up with the following. (below) Simple code that accepts some
string arguments, and prints a string -- so, of type String -> String
-> String -> String -> IO ().

I like to be concise, but I get the feeling something went awry.  What
seems to be costing me the most is checking whether the various
arguments are legitimate, and printing a helpful error message if not.

I was able to achieve this by using Maybe and error on failed pattern
match, but as said, seems kind of overly complicated.

Is there a simpler way to do the following, eg for function

  gen_gnuplot_financial_script :: String -> String -> String -> String ->
IO ()

?

By the way this is being used in

http://code.google.com/p/gnuplotwebinterface/

**

module Common where

gnuplot_png_settings = "set terminal png transparent nocrop enhanced
size 600,400\n" ++
   "set pm3d implicit at s"

gnuplot_math_settings =  gnuplot_png_settings ++ "\n" ++
 "set border 4095 \n\
 \  set xlabel \"x\" \n\
 \  set ylabel \"y\""

gnuplot_timeseries_settings = gnuplot_png_settings ++ "\n" ++
  "set xdata time   # The x axis
data is time \n" ++
  "set timefmt \"%d-%b-%y\" # The dates in
the file look like 10-Jun-04 \n" ++
  "set format x \"%b %d\"   #On the
x-axis, we want tics like Jun 10"


gen_gnuplot_math_script :: String -> String -> IO ()
gen_gnuplot_math_script style function = let maybePlotCmd = lookup
style style_to_plotcmd
 style_to_plotcmd =
[("math-2d","plot"),("math-3d","splot")]
   in case maybePlotCmd of
Just plotcmd ->
putStrLn $ gnuplot_math_settings ++ "\n" ++ plotcmd ++ " "  ++
function
_-> error
$ "bad style: " ++ style

gen_gnuplot_financial_script :: String -> String -> String -> String -> IO
()
gen_gnuplot_financial_script company displaymode startDate endDate
= let maybeCompanyFile = lookup company company_to_companyfile
  maybeModeString  = lookup displaymode displaymode_to_modestring
  maybeTitleEnd= lookup displaymode displaymode_to_titleend
  company_to_companyfile =
[("ibm","data/ibm.dat"),("cisco","data/cisco.dat")]
  displaymode_to_modestring = [("points", "using 1:2 with
linespoints"),
   ("candles","using
1:($2+$3+$4+$5)/4:4:3 with yerrorbars")]
  displaymode_to_titleend = [("points","daily
prices"),("candles","opening prices")]
in case ( maybeCompanyFile,
  maybeModeString,
  maybeTitleEnd ) of
( Just companyfile,
  Just modestring,
  Just titleEnd) -> putStrLn $
gnuplot_timeseries_settings ++ "\n" ++
  "plot [\"" ++ startDate ++ "\":\"" ++
endDate ++ "\"]"
  ++ " '" ++ companyfile ++ "'"
  ++ modestring
  ++ " title \"" ++ company ++ " " ++
titleEnd ++ "\""
_ -> error $ "bad lookup. " ++ company ++ " ->
company file: " ++ ( show maybeCompanyFile ) ++ "\n" ++
 "" ++ displaymode ++ " ->
displaymode: "  ++ ( show maybeModeString ) ++ "\n" ++
 "" ++ displaymode ++ " ->
titleEnd: " ++ ( show maybeTitleEnd)
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] more problems with c2hs

[Ruben Zilibowitz]

Hi,

I've built and installed c2hs on my Mac OS X system now. I read  
through the research paper on c2hs available on the website for c2hs  
and decided I would need to try it out to learn it. But it gives me  
errors which I am having trouble trying to understand. Here are the  
error messages:


c2hs file.chs

powerpc-apple-darwin8-gcc-4.0.1: c: No such file or directory
powerpc-apple-darwin8-gcc-4.0.1: c: No such file or directory
powerpc-apple-darwin8-gcc-4.0.1: warning: '-x -x' after last input  
file has no effect

powerpc-apple-darwin8-gcc-4.0.1: no input files
c2hs: Error during preprocessing custom header file

Can anyone figure out what is going on here? Is it my chs file or is  
it to do with c2hs?


Regards,

Ruben

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] linear algebra with Haskell (Was: Why Perl is more learnable than Haskell)

[Henning Thielemann]

On Wed, 11 Apr 2007, Ryan Dickie wrote:

> I also hate matlab to death. Is there any possibility of using haskell as a
> replacement using ghci? Mostly i care about linalg when it comes to using
> matlab.

Doing numerical linear algebra with Haskell is already possible:
 http://haskell.org/haskellwiki/Linear_algebra

If you can read German, you may want to share experiences on MatLab with
me:
 http://www.henning-thielemann.de/ScriptingHater.html#MatLab
:-)
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[R M]

 The link pretty much answers my question, though you probably require a
little bit more book keeping to get the indices out. Compared to the
iterative version or the matlab version, this definitely is more elegant,
but also is trickier. 


apfelmus wrote:
> 
> raghu vardhan <[EMAIL PROTECTED]>:
>> So, any algorithm that sorts is no good (think of n as huge, and k
>> small).
> 
> With lazy evaluation, it is!
> 
>   http://article.gmane.org/gmane.comp.lang.haskell.general/15010
> 
> 
> [EMAIL PROTECTED] wrote:
>> The essence of all the answers that you've received is that it doesn't
>> matter if k is small, sorting is still the most elegant answer in
>> Haskell.
> 
> (It's not only most elegant, it can even be put to work.)
> 
>> The reason is that in Haskell, a function which sort function will
>> produce the
>> sorted list lazily. If you don't demand the while list, you don't perform
>> the whole sort.
>> 
>> Some algorithms are better than others for minimising the amount of
>> work if not all of the list is demanded, but ideally, producing the
>> first k elements will take O(n log k + k) time.
> 
> You mean O(k * log n + n) of course.
> 
> Regards,
> apfelmus
> 
> ___
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

-- 
View this message in context: 
http://www.nabble.com/k-minima-in-Haskell-tf3563220.html#a9964572
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Yitzchak Gale]

\begin{code}

kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
 where
   (h, t) = splitAt k $ zip x [0..]

insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
| e < mx= Set.insert e s'
| otherwise = s
where
  (mx, s') = Set.deleteFindMax s

\end{code}

This gives O(log k * (n + k)) execution in constant memory.
If you need the result indices to be in order, you can put in
a sort at the end without changing the complexity.

This could be improved by a significant constant factor
by using a priority queue instead of Set. Any Edison people
out there?

Regards,
Yitz
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[Yitzchak Gale]

\begin{code}

kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
 where
   (h, t) = splitAt k $ zip x [0..]

insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
| e < mx= Set.insert e s'
| otherwise = s
where
  (mx, s') = Set.deleteFindMax s

\end{code}

This gives O(log k * (n + k)) execution in constant memory.
If you need the result indices to be in order, you can put in
a sort at the end without changing the complexity.

This could be improved by a significant constant factor
by using a priority queue instead of Set. Any Edison people
out there?

Regards,
Yitz
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Left-factoring with Parsec

[Joel Reymont]

How does

expr = b a*

translate back into the grammar? Assuming that I had b, c, d...

expr = b <|> c <|> d <|> many (do { symbol ":"; expr; symbol ":";  
expr })


Like this?

Thanks, Joel

On Apr 11, 2007, at 8:56 PM, Lennart Augustsson wrote:

I presume your grammar has other clauses for expr, otherwise the  
loop is inevitable.

Assuming you have other clauses you can always left-factor.

Here's how those of us with weak memory can remember how to do it:

Say that you have

  expr ::= expr ":" expr ":" expr
 | b
Let's call the part from the first ":" a, since it doesn't matter  
what it is.  So we have

  expr ::= expr a | b
Let's call expr x, and just change notation slightly
  x = x a + b
Now use high school algebra
  x = x*a + b
  x - x*a = b
  x*(1-a) = b
  x = b / (1-a)
  x = b * 1/(1-a)
Now you have to remember that the Taylor series expansion of 1/(1- 
a) is

  1/(1-a) = 1 + a + a^2 + a^3 + a^4 + ...

OK, now put your grammar hat back on.  What's
  1 | a | aa | aaa |  | ...
it's just an arbitrary number of a:s, i.e., a* (or 'many a' in  
parsec).

So finally
  expr = b a*

-- Lennart

On Apr 11, 2007, at 18:15 , Joel Reymont wrote:


Suppose I have expr = expr ":" expr ":" expr.

Can the above be left-factored to fail on empty input so that my  
parser doesn't go into a loop?


Thanks, Joel

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe




--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: k-minima in Haskell

[Steve Downey]

Does the answer change if the data source isn't a list, already in memory,
but a stream? That is, will the sort end up pulling the entire stream into
memory, when we only need k elements from the entire stream.

Interestingly, this is almost exactly the same as one of my standard
interview questions, with the main difference being looking for the k
elements closest to a target value, rather than the smallest. Not that it
really changes the problem, but recognizing that is one of the things I'm
looking for.

On 4/12/07, apfelmus <[EMAIL PROTECTED]> wrote:


raghu vardhan <[EMAIL PROTECTED]>:
> So, any algorithm that sorts is no good (think of n as huge, and k
small).

With lazy evaluation, it is!

  http://article.gmane.org/gmane.comp.lang.haskell.general/15010


[EMAIL PROTECTED] wrote:
> The essence of all the answers that you've received is that it doesn't
> matter if k is small, sorting is still the most elegant answer in
Haskell.

(It's not only most elegant, it can even be put to work.)

> The reason is that in Haskell, a function which sort function will
produce the
> sorted list lazily. If you don't demand the while list, you don't
perform
> the whole sort.
>
> Some algorithms are better than others for minimising the amount of
> work if not all of the list is demanded, but ideally, producing the
> first k elements will take O(n log k + k) time.

You mean O(k * log n + n) of course.

Regards,
apfelmus

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Left-factoring with Parsec

[Lennart Augustsson]

You need a "sequence" of b, and then a*.  So
  expr = do
p <- b <|> c <|> d
q <- many (...)
return ...

On Apr 12, 2007, at 20:04 , Joel Reymont wrote:


How does

expr = b a*

translate back into the grammar? Assuming that I had b, c, d...

expr = b <|> c <|> d <|> many (do { symbol ":"; expr; symbol ":";  
expr })


Like this?

Thanks, Joel

On Apr 11, 2007, at 8:56 PM, Lennart Augustsson wrote:

I presume your grammar has other clauses for expr, otherwise the  
loop is inevitable.

Assuming you have other clauses you can always left-factor.

Here's how those of us with weak memory can remember how to do it:

Say that you have

  expr ::= expr ":" expr ":" expr
 | b
Let's call the part from the first ":" a, since it doesn't matter  
what it is.  So we have

  expr ::= expr a | b
Let's call expr x, and just change notation slightly
  x = x a + b
Now use high school algebra
  x = x*a + b
  x - x*a = b
  x*(1-a) = b
  x = b / (1-a)
  x = b * 1/(1-a)
Now you have to remember that the Taylor series expansion of 1/(1- 
a) is

  1/(1-a) = 1 + a + a^2 + a^3 + a^4 + ...

OK, now put your grammar hat back on.  What's
  1 | a | aa | aaa |  | ...
it's just an arbitrary number of a:s, i.e., a* (or 'many a' in  
parsec).

So finally
  expr = b a*

-- Lennart

On Apr 11, 2007, at 18:15 , Joel Reymont wrote:


Suppose I have expr = expr ":" expr ":" expr.

Can the above be left-factored to fail on empty input so that my  
parser doesn't go into a loop?


Thanks, Joel

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe




--
http://wagerlabs.com/






___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Type checking with Haskell

[Lennart Augustsson]

It's so much easier to write the type checker because it's only a few  
constructs left in the language.  But from a user's perspective it's  
a really bad idea.


-- Lennart

On Apr 12, 2007, at 15:25 , Joel Reymont wrote:



On Apr 12, 2007, at 3:00 PM, Stefan O'Rear wrote:

Also, GHC runs typechecking *before* desugaring, apparently  
thinking error messages

are more important than programmer sanity :)


What would be the benefit of running type checking after desugaring?

--
http://wagerlabs.com/





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] more problems with c2hs

[Duncan Coutts]

On Fri, 2007-04-13 at 02:37 +1000, Ruben Zilibowitz wrote:
> Hi,
> 
> I've built and installed c2hs on my Mac OS X system now. I read  
> through the research paper on c2hs available on the website for c2hs  
> and decided I would need to try it out to learn it. But it gives me  
> errors which I am having trouble trying to understand. Here are the  
> error messages:
> 
> c2hs file.chs
> 
> powerpc-apple-darwin8-gcc-4.0.1: c: No such file or directory
> powerpc-apple-darwin8-gcc-4.0.1: c: No such file or directory
> powerpc-apple-darwin8-gcc-4.0.1: warning: '-x -x' after last input  
> file has no effect
> powerpc-apple-darwin8-gcc-4.0.1: no input files
> c2hs: Error during preprocessing custom header file

c2hs runs cpp -x c ${header}

for the header file you specify. You can either specify a header file on
the commend line or use #include's in the .chs file. c2hs should
generate a .h file itself in that case but it looks like it isn't for
some reason. You can find out what it is really doing by running:

c2hs --dump trace file.chs

btw, the better mailing list for this stuff is the c2hs mailing list:
[EMAIL PROTECTED]

Duncan

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Compiling GHC

[Chris Witte]

Awesome that works!
Thanks for your help.

Well that works for the ghc-6.7.20070402 tar ball but if I try and
pull down the darcs head it fails to make with

make[1]: Entering directory `/c/cwitte/source/ghc/libraries'
rm -f -f stamp/configure.library.*.base
cd base && setup/Setup configure \
 \
--prefix=/usr/local \
--with-compiler=../../compiler/ghc-inplace.bat \
--with-hc-pkg=../../utils/ghc-pkg/ghc-pkg-inplace.bat \
--with-hsc2hs=../../utils/hsc2hs/hsc2hs-inplace.bat \
--with-ld=/mingw/bin/ld \
--datasubdir=ghc \
--haddock-args="--use-contents=../index.html
--use-index=../doc-index.html" \
--configure-option=--with-cc=c:/mingw/bin/gcc.exe
The system cannot find the path specified.
make[1]: *** [stamp/configure.library.build.base] Error 1
make[1]: Leaving directory `/c/cwitte/source/ghc/libraries'
make: *** [stage1] Error 2

I wonder what has changed between then and now to cause this.

On 4/12/07, Andrew Appleyard <[EMAIL PROTECTED]> wrote:

On 11/04/2007, at 7:52 pm, Chris Witte wrote:
> I made this change but I still get the error
> unknown symbol `_gettimeofday'
> I'm using mingw 5.1.3 which as far as i can tell should use the
> 3.11 runtime.

Ensure that HAVE_GETTIMEOFDAY is defined in mk/config.h.

Also, I discovered that changes to Linker.c don't make it into
ghc.exe if you just do a 'make' in the base directory.  You need to
make the RTS, then link ghc with the new RTS.  The following commands
work for me (more typing, but a lot faster than making clean):

   make -C rts
   rm compiler/stage2/ghc.exe
   make -C compiler stage=2
   make install

Hope that helps.

Regards,
Andrew.


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] k-minima in Haskell

[ajb]

G'day all.

Quoting Kurt Hutchinson <[EMAIL PROTECTED]>:

> For my own edification, what is the benefit of this sortWith over sortBy?

None.  I wanted to write my own sort, illustrating how the lazy
evaluation thing works, and I didn't want a name clash with an
existing library function.

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Weaving fun

[Matthew Brecknell]

Jan-Willem Maessen:
> Interestingly, in this particular case what we obtain is isomorphic  
> to constructing and reversing a list.

Jan-Willem's observation also hints at some interesting performance
characteristics of difference lists. It's well known that difference
lists give O(1) concatenation, but I haven't seen much discussion of the
cost of conversion to ordinary lists.

The conversion cost seems to be O(n), where n is the number of
concatenations performed to build the difference list. Since the cost of
building such a difference list is already O(n), the conversion cost
only becomes significant if a difference list is converted more than
once. Of course, the cost of consuming any one of those conversions is
also likely to be at least O(n), so we see why this doesn't get much
attention.

Slightly more interesting is the observation that the grouping of
difference list concatenations has a significant impact on the
conversion cost, and in particular, on when the cost is incurred. When
concatenations are grouped to the right, we get lazy conversion. Grouped
to the left, we get strict(er) conversion.

To see this, consider what happens if we take the heads of two
difference lists, with concatenations grouped to the right and left
respectively:

> head_r n = head ((foldr1 (.) (map (:) [1..n])) [])
> head_l n = head ((foldl1 (.) (map (:) [1..n])) [])

We find that head_r is O(1), and head_l is O(n). Writing out the
conversion for a left-grouped difference list, we also see Jan-Willem's
reverse isomorphism quite clearly:

head 1:).(2:)).(3:)) [])
==> head (((1:).(2:)) (3:[]))
==> head ((1:) (2:3:[]))
==> head (1:2:3:[])
==> 1

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: k-minima in Haskell

[Dan Weston]

Ah, but which k elements? You won't know until you've drained your 
entire stream!


Dan

Steve Downey wrote:
Does the answer change if the data source isn't a list, already in 
memory, but a stream? That is, will the sort end up pulling the entire 
stream into memory, when we only need k elements from the entire stream.


Interestingly, this is almost exactly the same as one of my standard 
interview questions, with the main difference being looking for the k 
elements closest to a target value, rather than the smallest. Not that 
it really changes the problem, but recognizing that is one of the things 
I'm looking for.


On 4/12/07, *apfelmus* <[EMAIL PROTECTED] 
> wrote:


raghu vardhan <[EMAIL PROTECTED] >:
 > So, any algorithm that sorts is no good (think of n as huge, and
k small).

With lazy evaluation, it is!

   http://article.gmane.org/gmane.comp.lang.haskell.general/15010


[EMAIL PROTECTED]  wrote:
 > The essence of all the answers that you've received is that it
doesn't
 > matter if k is small, sorting is still the most elegant answer in
Haskell.

(It's not only most elegant, it can even be put to work.)

 > The reason is that in Haskell, a function which sort function
will produce the
 > sorted list lazily. If you don't demand the while list, you don't
perform
 > the whole sort.
 >
 > Some algorithms are better than others for minimising the amount of
 > work if not all of the list is demanded, but ideally, producing the
 > first k elements will take O(n log k + k) time.

You mean O(k * log n + n) of course.

Regards,
apfelmus

___
Haskell-Cafe mailing list
[EMAIL PROTECTED] 
http://www.haskell.org/mailman/listinfo/haskell-cafe





___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe



___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] xmonad window manager mailing list

[Donald Bruce Stewart]

I'm pleased to announce that the xmonad window manager now
has a mailing list set up:

http://www.haskell.org/mailman/listinfo/xmonad

For those who don't know, xmonad is a tiling window manager written in
Haskell. You can find more about it at:

http://xmonad.org

and Lennart Kolmodin's recent blog post

http://lennartkolmodin.blogspot.com/2007/04/xmonad.html

Additionally, the lead xmonad developer, Spencer Janssen, has been
accepted by PSU to work on XCB bindings to Haskell, for the Google
Summer of Code. XCB is a simpler, smaller, threadsafe replacement for
Xlib, which should simplify further the window manager code base.

We hope to have the 0.1 release of xmonad out shortly, until then, hope
to see you on the mailing list!

-- Don
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: k-minima in Haskell

[Mark T.B. Carroll]

Dan Weston <[EMAIL PROTECTED]> writes:

> Ah, but which k elements? You won't know until you've drained your 
> entire stream!

True, but you still don't need to keep the whole stream in memory at
once, just the k-least-so-far as you work your way through the stream -
once you've read a part of the stream you can mostly forget it again.
The question as I understood it was one of if even in Haskell there's a
better way than sorting that means you need only have a fragment of the
stream in memory at once.

-- Mark

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: k-minima in Haskell

[Nicolas Frisby]

Both Yitzchak's and my suggestions should run in constant space--some
strictness annotation or switching to foldl' might be necessary.

On 4/12/07, Mark T.B. Carroll <[EMAIL PROTECTED]> wrote:

Dan Weston <[EMAIL PROTECTED]> writes:

> Ah, but which k elements? You won't know until you've drained your
> entire stream!

True, but you still don't need to keep the whole stream in memory at
once, just the k-least-so-far as you work your way through the stream -
once you've read a part of the stream you can mostly forget it again.
The question as I understood it was one of if even in Haskell there's a
better way than sorting that means you need only have a fragment of the
stream in memory at once.

-- Mark

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: k-minima in Haskell

[ajb]

G'day all.

Quoting apfelmus <[EMAIL PROTECTED]>:

> You mean O(k * log n + n) of course.

Erm, yes.  You can do it in an imperative language by building a heap
in O(n) time followed by removing k elements, in O(k log n) time.

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Compiling GHC

[Andrew Appleyard]

On 13/04/2007, at 11:03 am, Chris Witte wrote:

Well that works for the ghc-6.7.20070402 tar ball but if I try and
pull down the darcs head it fails to make with
...
I wonder what has changed between then and now to cause this.


Not sure about that one, I was building ghc-6.6.  Darcs should be  
able to help you find the changes, of course which ones are causing  
the problem is another story...


Regards,
Andrew.


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Export Haskell Libraries

[SevenThunders]

I've finished a good sized Haskell project which I now must expose as a
library (along with a lot of C code) to my fellow engineers.  I had
originally devoped my code on Windows XP and managed to learn how to wrap my
Haskell code in a DLL and create an MSVC linkable library stub for the DLL. 
Although involved, the output in windows is relatively transparent in that
as long as the paths are available to the Haskell runtime libraries and my
DLL, linking is straightforward.

Now however I find I must export the same libraries to linux.  I decided to
get 'smart' and repackage my build tools using CMAKE and cabal.  Building
the C object files is no problem and even configuring Cabal to generate my
executables is not too painful.  However the pain begins when one tries to
link any Haskell object files or libraries to an external C program.  Using
ghc -v during the build reveals that gcc has about 50 -u flag arguments and
links to 9 or 10 different libraries.Given that my little component is
just a tiny part of a large software project involving many more engineers
and many man years of work,  it's not going to be fun to link my little
library using all these crazy build flags to a large external project,
especially when order is important.  Wouldn't it be nice if there were a
single run time library I could link to, (or even generate on the fly) that
didn't have this intricate build step.  How is ghc/Haskell supposed to
integrate with the rest of the software world?

A related issue in the building of my export libraries is cabal itself.  I
want to package my own library with some external object files etc and some
Haskell code.  It's easily done with ar and the correct object files. 
Unfortunately it is not clear from the documentation how I can force cabal
to place the object files and generated stub files in a place where I can
use them.  (CMake is kind of forcing me to have them reside with the source
for reasons I don't want to go into here.)   I instead find myself copying
the object files (*.o) back into the source directory from an obscure tmp
directory several layers down from the source directory.   This is not
particularly portable and is probably quite fragile once someone decides to
change the directory hiearcharchy in cabal.

I guess I am surprised that on linux, with all of it's amazing software
development tools, that Haskell export libraries would be this tricky to
develop.


-- 
View this message in context: 
http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9972866
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Export Haskell Libraries

[Duncan Coutts]

On Thu, 2007-04-12 at 21:48 -0700, SevenThunders wrote:

> I guess I am surprised that on linux, with all of it's amazing software
> development tools, that Haskell export libraries would be this tricky to
> develop.

I guess it's because most of the existing Haskell hackers are going the
other direction, they build Haskell programs that use external C libs,
but the top level of the system is always Haskell. It's much more rare
for these people to want to include a Haskell component into another
system.

So it's easy if you link the system using ghc. If you want to link it
all using gcc instead, yeah, that's a bit harder. You can see most of
the flags ghc passes to gcc as they're just in the package configuration
for the rts and base packages (ghc-pkg display rts / base). It should be
fairly straightforward to generate a gnu linker script from all this
that you could use with gcc when linking your whole system. By tucking
the ghc flags away in a linker scrupt you will not terrify your fellow
developers with all the odd -u flags.

As for the issue of cabal putting generated files in a directory other
than the source tree, you can tell cabal exactly which directory to use,
so it's not that non-portable to go grubbing around in it to find the .o
files you need to link into the archive file.

Alternatively you could just let cabal build the .a file. It can include
externally generated .o files into the archive. Alternatively you can
just use two .a files, keeping your other .o's in a separate file. Or
you could even combine the two archives together as a later build step.


Actually it's not too bad if you ignore all the 50 -u flags. Apart from
that, the "single runtime library" you want is just three: HSbase,
HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp,
dl and rt.

There is a project for this year's Google Summer of Code to use dynamic
libraries on Linux. Perhaps this would make the situation better for you
since dynamic libs record their own dependencies much better. Ideally
you would only have to link to your own Haskell package built as a .so
and that would pull in the dependencies on HSbase.so, HSrts.so and the
other system libs.

Duncan

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Export Haskell Libraries

[SevenThunders]

Duncan Coutts wrote:
> 
> 
> 
> So it's easy if you link the system using ghc. If you want to link it
> all using gcc instead, yeah, that's a bit harder. You can see most of
> the flags ghc passes to gcc as they're just in the package configuration
> for the rts and base packages (ghc-pkg display rts / base). It should be
> fairly straightforward to generate a gnu linker script from all this
> that you could use with gcc when linking your whole system. By tucking
> the ghc flags away in a linker scrupt you will not terrify your fellow
> developers with all the odd -u flags.
> 
That was my first thought and in fact I did write such a script.  The only
problem is
I'm afraid that the link stages for the software I have integrate to may be
rather complex
and I thought that maybe this would not be the best approach if there were
order dependencies
etc.  But maybe it's not so bad.  In the end I managed to capture all the
dependencies in CMake
so I'm hoping that will make it a little easier to do the final integration.



> As for the issue of cabal putting generated files in a directory other
> than the source tree, you can tell cabal exactly which directory to use,
> so it's not that non-portable to go grubbing around in it to find the .o
> files you need to link into the archive file.
> 
I saw a lot of options for places to put sources and targets, but I couldn't
quite
figure out how to configure it to place the object file output.  No doubt
it's there, I just couldn't
find it in the 45 min.s or so that I looked for it.



> Alternatively you could just let cabal build the .a file. It can include
> externally generated .o files into the archive. Alternatively you can
> just use two .a files, keeping your other .o's in a separate file. Or
> you could even combine the two archives together as a later build step.
> 
Yes, this would be an attractive approach I think.  Is it a matter of
passing the correct flags to ghc,
 Ghc-options:  -?
At first glance, looking at the basic tutorial it seemed like to build a
library one uses a line like
Exposed Modules: A B C
However I thought this would build Haskell only libraries.Then there is
the business of merging libraries, which I suppose is done with ar and
ranlib  by extracting all the object files from one library and then adding
them back in to the other.  If it had to portable to windows as well I
wonder if this would work.




> Actually it's not too bad if you ignore all the 50 -u flags. Apart from
> that, the "single runtime library" you want is just three: HSbase,
> HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp,
> dl and rt.
> 
running ghc -v for all my haskell code forced me to link to these libraries
ultimately:
HShaskell98 HSregex-compat HSregex-posix
HSregex-base HSparsec HSbase
HSbase_cbits HSrts m gmp dl rt



> There is a project for this year's Google Summer of Code to use dynamic
> libraries on Linux. Perhaps this would make the situation better for you
> since dynamic libs record their own dependencies much better. Ideally
> you would only have to link to your own Haskell package built as a .so
> and that would pull in the dependencies on HSbase.so, HSrts.so and the
> other system libs.
> 
> Duncan
> 
Then it would be very similar to the windows build steps and probably a bit
easier since one wouldn't have
to mess with dlltools and converting libraries to ms vc formats etc.  Really
all that's needed though is a tool that can automagically wrap a homegrown
static or even dynamic library that contains the needed components of the
GHC run time library along with the additional user code.  I know all the
object files are available as are of course the libraries themselves, so
such a script is not impossible.  It seems that ghc itself is doing some
kind of dependency analysis to determine the final call to gcc.

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe


-- 
View this message in context: 
http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9973642
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe