Re: [Haskell-cafe] simple servers
>> All system calls issued from the network package use non-blocking. >> You don't have to worry about blocking at all. > > Almost. Especially when interfacing with C code you should include the > "-threaded" option to GHC to link against the multi-threaded run-time > system. Otherwise your Haskell code will block your C code and > vice-versa. Also some concurrency features don't work properly in the > single-threaded run-time. Non-threaded RTS would block FFI to C code. But it does not block file descriptors and sockets because the scheduler uses select(). To my experience, *simple* network programming with non-threaded RTS also works well except the case where we reach the limit of file descriptors for the process. Anyway, I recommend to specify the "-threaded" option to GHC for network programming if you don't have special reasons. --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simple servers
Kazu Yamamoto (山本和彦) wrote: > > One last question. When writing C code, using epoll apis explicitly > > can impose some blocking. Is the same to be said for GHC.Event? > > I don't understand your question. > > All system calls issued from the network package use non-blocking. > You don't have to worry about blocking at all. Almost. Especially when interfacing with C code you should include the "-threaded" option to GHC to link against the multi-threaded run-time system. Otherwise your Haskell code will block your C code and vice-versa. Also some concurrency features don't work properly in the single-threaded run-time. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] An easy way to represent and modify graphs?
Pointers. Seriously. In Haskell one could use STRef rather than the cumbersome Foreign.Ptr, though STRef too can be kludgy. I know not whether safe, pure, immutable pointers would be possible in Haskell, but in my experience STRef can work well enough. Cheers, Strake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Weekly News: Issue 244
Welcome to issue 244 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of September 9 to September 15, 2012. Inbox As you might have heard, GHC 7.6.1 is out for all platforms. I would say "get it while it is still hot", but I guess I missed my opportunity to do that last week. [1] http://goo.gl/0fwDQ Sonke Hahn wrote in to announce that on Monday "Story Episodes of Nikki and the Robots" was was released. [2] http://goo.gl/dBifT Malcolm Wallace has uploaded videos from ICFP 2012, for those of us that didn't have the opportunity to be there. Big thanks for sharing these with the community! [3] http://goo.gl/6ZhYV Quotes of the Week * copumpkin: when in doubt, blame ski * shachaf: You can call the greengrocer and place an order. That'll convert their unordered pears into ordered pears! * shachaf: Those who would give up essential type independence for a little temporary type safety deserve neither independence nor safety. * ddarius: edwardk: So your plan for Haskell adoption is to write Haskell in languages that aren't Haskell, say "Man, these languages suck, this would be super easy in Haskell", and then use the Haskell you started with reproducing functionality at an "unbelievable" rate. * cmccann: personally I'm just waiting for an extension that demotes types to the value level, so that we can finally have natural numbers. Top Reddit Stories * Yet another Haskell IDE in the works Domain: yesodweb.com, Score: 71, Comments: 94 On Reddit: [4] http://goo.gl/N1nfs Original: [5] http://goo.gl/z47p8 * The case of the mysterious explosion in space Domain: serpentine.com, Score: 65, Comments: 9 On Reddit: [6] http://goo.gl/O782g Original: [7] http://goo.gl/eQxOc * Haskell vs. F# vs. Scala: A High-level Language Features and Parallelism Support Comparison Domain: macs.hw.ac.uk, Score: 47, Comments: 30 On Reddit: [8] http://goo.gl/XWdPX Original: [9] http://goo.gl/daRy2 * The functor design pattern Domain: haskellforall.com, Score: 42, Comments: 45 On Reddit: [10] http://goo.gl/FpJL4 Original: [11] http://goo.gl/pZ4yu * How To Exclude Women From Your Technical Community: A Tutorial Domain: tim.dreamwidth.org, Score: 42, Comments: 309 On Reddit: [12] http://goo.gl/iKN7H Original: [13] http://goo.gl/GKMjb * A simple library that allows logic programming in Haskell Domain: github.com, Score: 38, Comments: 10 On Reddit: [14] http://goo.gl/J9Pbp Original: [15] http://goo.gl/1bRw5 * Larry Wall: "You should probably know about it [Haskell] if only to be able to say 'is this like Haskell?', and, if so, then you know you'll have to hire some really smart people to program in it." Domain: youtube.com, Score: 34, Comments: 130 On Reddit: [16] http://goo.gl/z1PTW Original: [17] http://goo.gl/5bCN9 * Malcolm Wallace is broadcasting videos from ICFP Domain: m.youtube.com, Score: 33, Comments: 9 On Reddit: [18] http://goo.gl/O6uuy Original: [19] http://goo.gl/Kyg5O * Darcs hub alpha: a darcsden fork to “turn the dogfooding knobs up to 11” Domain: hub.darcs.net, Score: 30, Comments: 10 On Reddit: [20] http://goo.gl/5D614 Original: [21] http://goo.gl/pDHL9 * The Architecture of the Mighttpd High-Speed Web Server Domain: iij.ad.jp, Score: 28, Comments: 4 On Reddit: [22] http://goo.gl/7yRbw Original: [23] http://goo.gl/oCkBt * Tying the knot on a Rubik's cube Domain: self.haskell, Score: 25, Comments: 7 On Reddit: [24] http://goo.gl/0XPiY Original: [25] http://goo.gl/0XPiY * Kazu Yamamoto: Improving the performance of Warp Domain: yesodweb.com, Score: 24, Comments: 1 On Reddit: [26] http://goo.gl/yvRfR Original: [27] http://goo.gl/gEQlA * Taking advantage of "Theorems for Free"? Domain: self.haskell, Score: 20, Comments: 9 On Reddit: [28] http://goo.gl/cqy6U Original: [29] http://goo.gl/cqy6U Top StackOverflow Questions * Is there a nice way to make function signatures more informative in Haskell? votes: 37, answers: 6 Read on SO: [30] http://goo.gl/vOY98 * Purely functional data structures for text editors votes: 26, answers: 7 Read on SO: [31] http://goo.gl/ciJQ3 * Lazy Pattern matching in Data.List votes: 15, answers: 1 Read on SO: [32] http://goo.gl/T2YPC * Can I provide the type-checker with proofs about inductive naturals in GHC 7.6? votes: 14, answers: 1 Read on SO: [33] http://goo.gl/zoMDr * Why does Haskell's “flip id” has this type? votes: 12, answers: 1 Read on SO: [34] http://goo.gl/HWuyZ * How long pauses can occur in a Haskell program due to garbage collection? votes: 11, answers: 1 Read on SO: [35] http://goo.gl/Stnq7 * Good introduction to f
Re: [Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists
On Wed, Sep 19, 2012 at 8:36 PM, wren ng thornton wrote:
>> P.S. It is actually possible to write zip function using Boehm-Berarducci
>> encoding:
>> http://okmij.org/ftp/ftp/Algorithms.html#zip-folds
>
>
> Of course it is; I just never got around to doing it :)
If you do, you might want to consider not using the above method, as I
seem to recall it doing an undesirable amount of extra work (repeated
O(n) tail). One can do better with some controversial types (this is
not my idea originally; ski (don't know his real name) on freenode's
#haskell showed it to me a long time ago):
snip
{-# LANGUAGE PolymorphicComponents #-}
module ABC where
newtype L a = L { unL :: forall r. (a -> r -> r) -> r -> r }
nil :: L a
nil = L $ \_ z -> z
cons :: a -> L a -> L a
cons x (L xs) = L $ \f -> f x . xs f
newtype A a c = Roll { unroll :: (a -> A a c -> L c) -> L c }
type B a c = a -> A a c -> L c
zipWith :: (a -> b -> c) -> L a -> L b -> L c
zipWith f (L as) (L bs) = unroll (as consA nilA) (bs consB nilB)
where
-- nilA :: A a c
nilA = Roll $ const nil
-- consA :: a -> A a c -> A a c
consA x xs = Roll $ \k -> k x xs
-- nilB :: B a c
nilB _ _ = nil
-- consB :: b -> B a c -> B a c
consB y ys x xs = f x y `cons` unroll xs ys
snip
This traverses each list only once.
-- Dan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simple servers
Hi, > Is it true that writing a simple server using forkIO now integrates > native event loops implicitly? Yes. IO manager handles event driven stuff. Thanks to this, we can enjoy (light) thread programming using forkIO. > One last question. When writing C code, using epoll apis explicitly > can impose some blocking. Is the same to be said for GHC.Event? I don't understand your question. All system calls issued from the network package use non-blocking. You don't have to worry about blocking at all. P.S. This article would help: http://www.iij.ad.jp/en/company/development/tech/mighttpd/ --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Church vs Boehm-Berarducci encoding of Lists
On 9/18/12 4:27 AM, o...@okmij.org wrote:
There has been a recent discussion of ``Church encoding'' of lists and
the comparison with Scott encoding.
I'd like to point out that what is often called Church encoding is
actually Boehm-Berarducci encoding. That is, often seen
newtype ChurchList a =
CL { cataCL :: forall r. (a -> r -> r) -> r -> r }
(in http://community.haskell.org/%7Ewren/list-extras/Data/List/Church.hs )
is _not_ Church encoding. First of all, Church encoding is not typed
and it is not tight.
I know that Church encodings were explored in the untyped setting (and
hence cannot be tight); but I was unaware of a citation for the typed
version of the same encoding. I've since corrected the names of the
above module.
N.B., for folks following along at home, the above module and the Scott
version aren't actually in list-extras yet. I just dumped them there for
lack of somewhere else to stash the code from last time this comparison
came up.
P.S. It is actually possible to write zip function using Boehm-Berarducci
encoding:
http://okmij.org/ftp/ftp/Algorithms.html#zip-folds
Of course it is; I just never got around to doing it :)
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] foldl vs. foldr
On 9/18/12 8:32 AM, Jan Stolarek wrote: Hi list, I have yet another question about folds. Reading here and there I encountered statements that foldr is more important than foldl, e.g. in this post on the list: http://www.haskell.org/pipermail/haskell-cafe/2012-May/101338.html I want to know are such statements correct and, if so, why? I am aware that foldl' can in some circumstances operate in constant space, while foldr can operate on infinite lists if the folding function is lazy in the second parameter. Is there more to this subject? Properties that I mentioned are more of technical nature, not theoretical ones. Are there any significant theoretical advantages of foldr? I read Bird's and Wadler's "Introduction to functional programming" and it seems to me that foldl and foldr have the same properties and in many cases are interchangeable. The interchangeability typically arises from the (weak) isomorphism between: data CList a = CNil | Cons a (CList a) data SList a = SNil | Snoc (SList a) a In particular, interchangeability will fail whenever the isomorphism fails--- namely, for infinite lists. However, there is another issue at stake. The right fold is the natural catamorphism for CList, and we like catamorphisms because they capture the definability class of primitive recursive functions[1]. However, catamorphisms inherently capture a bottom-up style of recursion (even though they are evaluated top-down in a lazy language). There are times when we'd rather capture a top-down style of recursion--- which is exactly what left folds do[2]. Unfortunately, left folds have not been studied as extensively as right folds. So it's not entirely clear what their theoretical basis is, or how exactly their power relates to right folds. [1] That is, every primitive recursive *function* can be defined with a catamorphism. However, do note that this may not be the most efficient *algorithm* for that function. Paramorphisms thus capture the class better, since they can capture more efficient algorithms than catamorphisms can. If you're familiar with the distinction between "iterators" (cata) and "recursors" (para), this is exactly the same thing. [2] Just as paramorphisms capture algorithms that catamorphisms can't, left folds capture algorithms that right folds can't; e.g., some constant stack/space algorithms. Though, unlike cata vs para, left folds do not appear to be strictly more powerful. Right folds can capture algorithms that left folds (apparently) can't; e.g., folds over infinite structures. I say "apparently" because once you add scanl/r to the discussion instead of just foldl/r, things get a lot murkier. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [ANNOUNCE] Fmark markup language
On 12-09-18 07:37 PM, Richard O'Keefe wrote: On 19/09/2012, at 1:43 AM, Stefan Monnier wrote: The problem with that is that some people DO end some headings with a full stop; for them your special syntax is not natural. Markdown/ReST is already using the "no syntax" idea (e.g. compared to pre-wiki markup such a LaTeX or Texinfo), so he's simply trying to push this idea further. Markdown is very heavy on syntax, what it is *light* on is specification of what the syntax actually is. As a result, I'm aware of three different dialects, and someone told me about having to reverse engineer the syntax from a Perl implementation. As a further result, I cannot write a program to reliably *generate* Markdown. Very true. Sadly, this is the case with almost all other Wiki-like markup schemes out there. They are all implementation-specified. The only exception I'm aware of is Creole, for which an EBNF grammar exists, even if it's pretty nasty-looking. A look at that specification makes one appreciate how badly specified "natural" syntax is. In my opinion, there is no single natural syntax that can be imposed on ASCII strings and serve majority of uses. There are many different syntaxes that feel natural for different uses and different users, and the best we can hope to achieve would be a way to provide a formal and readable specification for each of those syntaxes. I've been playing with one approach in this direction with the concrete-relaxng-parser package, but it's still early days. I suspect it'll be difficult. Oh, more power to him for trying. I just don't think it can be pushed very far. Oh, there is a really *filthy* hack that could be pulled for italics, bold face, and so on. Contrary to its original principles, Unicode includes several copies of ASCII (see http://unicode.org/charts/PDF/U1D400.pdf): Mathematical bold, Mathematical italic, Mathematical bold italic, Mathematical script, Mathematical bold script, Mathematical fraktur, Mathematical double struck (blackboard-bold), Mathematical bold fraktur, Mathematical sans-serif, Mathematical sans-serif bold, Mathematical sans-serif italic, Mathematical sans-serif bold italic, Mathematical monospace, and some similar sets of Greek. Thank you for sharing this hack. It's very amusing. -- Mario Blazevic mblaze...@stilo.com Stilo International This message, including any attachments, is for the sole use of the intended recipient(s) and may contain confidential and privileged information. Any unauthorized review, use, disclosure, copying, or distribution is strictly prohibited. If you are not the intended recipient(s) please contact the sender by reply email and destroy all copies of the original message and any attachments. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUCE: one-liner-0, SYB-like generics with constraint kinds
Hi all,
I am pleased to announce the first release of One-Liner, a package for writing
short and concise generic instances of type classes. It works a bit like
Scrap-Your-Boilerplate, but it uses the new constraint kinds instead of the
Typeable class.
On hackage: http://hackage.haskell.org/package/one-liner-0
On github: https://github.com/sjoerdvisscher/one-liner
For example, this is how to write generic equality (using the All monoid):
eqADT :: (ADT t, Constraints t Eq) => t -> t -> Bool
eqADT s t = ctorIndex s == ctorIndex t &&
getAll (mbuilds (For :: For Eq) (\fld -> All $ s ! fld == t ! fld) `at` s)
The code works like this: "Constraints t Eq" means it requires that all
subcomponents of type t have an Eq instance, and then values s and t are equal
if they are built by the same constructor and each subcomponent is equal.
The package is called One-Liner because the generic functions often end up as
short as eqADT, especially if there's already an appropriate Monoid or
Applicative functor available.
Here are two more examples, generic put and get for the Binary package (after
adding the missing Monoid instance for Put)
putADT :: (ADT t, Constraints t Binary) => t -> Put
putADT t = putWord8 (toEnum (ctorIndex t)) >> gfoldMap (For :: For Binary) put
getADT :: (ADT t, Constraints t Binary) => Get t
getADT = do
ix <- fromEnum <$> getWord8
buildsA (For :: For Binary) (const get) !! ix
Finally, to give a complete sense of what's involved, here's an example data
type and its ADT implementation:
data T a = A Int a | B a (T a)
instance ADT (T a) where
ctorIndex A{} = 0
ctorIndex B{} = 1
type Constraints (T a) c = (c Int, c a, c (T a))
buildsRecA For sub rec =
[ (ctor "A", A <$> sub (FieldInfo (\(A i _) -> i)) <*> sub (FieldInfo
(\(A _ a) -> a)))
, (ctor "B", B <$> sub (FieldInfo (\(B a _) -> a)) <*> rec (FieldInfo
(\(B _ t) -> t)))
]
If you want to learn more, you can find an introductory blog post here:
https://github.com/sjoerdvisscher/blog/blob/master/2012/2012-09-06%20constraint-based%20generics.md
Some complete examples are here:
https://github.com/sjoerdvisscher/one-liner/tree/master/examples
Some more generic functions, including generic Show and Read:
https://github.com/sjoerdvisscher/one-liner/blob/master/src/Generics/OneLiner/Functions.hs
--
Sjoerd Visscher
https://github.com/sjoerdvisscher/blog
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
On Wed, Sep 19, 2012 at 8:00 PM, wrote: > So how do I force IO actions whose results are discarded (including IO ()) to > be strict? In your particular case it looks like you want Data.IORef.modifyIORef'. If your version of GHC doesn't include it you can write it like so: -- |Strict version of 'modifyIORef' modifyIORef' :: IORef a -> (a -> a) -> IO () modifyIORef' ref f = do x <- readIORef ref let x' = f x x' `seq` writeIORef ref x' -- Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
Hi! On 19/09/12 19:00, sdiy...@sjtu.edu.cn wrote: > So how do I force IO actions whose results are discarded (including IO ()) to > be strict? () <- foo :: IO () -- should work as it pattern matches, can wrap it in a prettier combinator !_ <- foo :: IO a -- could work with -XBangPatterns I've not tested either (been away from Haskell for a while..), but see also: http://markmail.org/message/i7eufihlhgq4jqt6 (regarding modifyIORef and leaky issues) Claude -- http://mathr.co.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
So how do I force IO actions whose results are discarded (including IO ()) to be strict? main = do s<-newIORef (1::Int) let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n !acc = do v <- modifyIORef s (+2) >>readIORef s -- reading immediately after writing f (n-1) (v+acc) f 100 100 >>= print readIORef s>>=print runs OK, while main = do s<-newIORef (1::Int) let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n !acc = do v <- modifyIORef s (+2) >>return 1 f (n-1) (v+acc) f 100 100 >>= print readIORef s>>=print , main = do s<-newIORef (1::Int) let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n !acc = do v <- modifyIORef s (+2) >>readIORef s>>return 1 f (n-1) (v+acc) f 100 100 >>= print readIORef s>>=print and main = do s<-newIORef (1::Int) let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n !acc = do v <- (>>return 1) $! (modifyIORef s (+2) >>readIORef s) f (n-1) (v+acc) f 100 100 >>= print readIORef s>>=print all overflows after correctly printing the first number - 原始邮件 - 发件人: "Johan Tibell" 收件人: sdiy...@sjtu.edu.cn 抄送: haskell-cafe@haskell.org 发送时间: 星期四, 2012年 9 月 20日 上午 1:28:47 主题: Re: [Haskell-cafe] How to implement nested loops with tail recursion? On Wed, Sep 19, 2012 at 7:24 PM, wrote: > main = do > let > f 0 acc = return acc > f n acc = do > v <- return 1 > f (n-1) (v+acc) > f 100 100 >>= print Try this main = do let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n acc = do v <- return 1 f (n-1) (v+acc) f 100 100 >>= print ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
On Wed, Sep 19, 2012 at 7:24 PM, wrote: > main = do > let > f 0 acc = return acc > f n acc = do > v <- return 1 > f (n-1) (v+acc) > f 100 100 >>= print Try this main = do let f :: Int -> Int -> IO Int f 0 !acc = return acc -- note strict accumulator f n acc = do v <- return 1 f (n-1) (v+acc) f 100 100 >>= print ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
A follow-up question.
I still haven't got the monadic version working, and the real use case involves
IO actions.
I looked at http://www.haskell.org/haskellwiki/Recursion_in_a_monad and adapted
the 'tail-recursive' snippet on the page into
main = do
let
f 0 acc = return acc
f n acc = do
v <- return 1
f (n-1) (v+acc)
f 100 100 >>= print
which still blows the memory.
And so does this program
main = do
s<-newIORef (0::Int)
mapM_ (\i->modifyIORef s (+1)) [0..1000]
readIORef s>>=print
Why?
- 原始邮件 -
发件人: sdiy...@sjtu.edu.cn
收件人: haskell-cafe@haskell.org
发送时间: 星期四, 2012年 9 月 20日 上午 12:08:19
主题: Re: How to implement nested loops with tail recursion?
Now I have discovered the right version...
main = print (f 1 0::Int) where
f i s = (if i<=2 then (f (i+1) (s + g 1 0)) else s) where
g j s = (if j<=2 then (g (j+1) (s + i*j)) else s)
- 原始邮件 -
发件人: sdiy...@sjtu.edu.cn
收件人: haskell-cafe@haskell.org
发送时间: 星期三, 2012年 9 月 19日 下午 11:35:11
主题: How to implement nested loops with tail recursion?
I need to implement fast two-level loops, and I am learning using seq to make
calls tail-recursive.
I write programs to compute
main = print $ sum [i*j|i::Int<-[1..2],j::Int<-[1..2]]
This program (compiled with -O2) runs twenty times slower than the unoptimized
(otherwise the loop gets optimized out) C version.
But it seems to run in constant memory, so I assume that it has been turned
into loops.
#include
int main(){
int s=0;
for(int i=1;i<=2;++i){
for(int j=1;j<=2;++j){
s+=i*j;
}
}
printf("%d\n",s);
return 0;
}
Then I write
main = print $ f 1 where
f i = let x = g 1 in x `seq` (x + if i<2 then f (i+1) else 0) ::
Int where
g j = let x = i*j in x `seq` (x + if j<2 then g (j+1) else
0) :: Int
This version runs out of memory. When I scale the numbers down to 1, the
program does run correctly, and takes lots of memory.
Even if I change the seqs into deepseqs, or use BangPatterns (f !i =... ; g !j
= ...), the situation doesn't change.
A monadic version
import Control.Monad.ST.Strict
import Control.Monad
import Data.STRef.Strict
main = print $ runST $ do
s <- newSTRef (0::Int)
let g !i !j =
if (j<=1) then modifySTRef s (+1)>>(g i (j+1)) else return
()
let f !i =
if (i<=1) then g i 1>>(f $ i+1) else return ()
f 1
readSTRef s
also runs out of memory.
So how can I write a program that executes nested loops efficiently?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to implement nested loops with tail recursion?
Now I have discovered the right version...
main = print (f 1 0::Int) where
f i s = (if i<=2 then (f (i+1) (s + g 1 0)) else s) where
g j s = (if j<=2 then (g (j+1) (s + i*j)) else s)
- 原始邮件 -
发件人: sdiy...@sjtu.edu.cn
收件人: haskell-cafe@haskell.org
发送时间: 星期三, 2012年 9 月 19日 下午 11:35:11
主题: How to implement nested loops with tail recursion?
I need to implement fast two-level loops, and I am learning using seq to make
calls tail-recursive.
I write programs to compute
main = print $ sum [i*j|i::Int<-[1..2],j::Int<-[1..2]]
This program (compiled with -O2) runs twenty times slower than the unoptimized
(otherwise the loop gets optimized out) C version.
But it seems to run in constant memory, so I assume that it has been turned
into loops.
#include
int main(){
int s=0;
for(int i=1;i<=2;++i){
for(int j=1;j<=2;++j){
s+=i*j;
}
}
printf("%d\n",s);
return 0;
}
Then I write
main = print $ f 1 where
f i = let x = g 1 in x `seq` (x + if i<2 then f (i+1) else 0) ::
Int where
g j = let x = i*j in x `seq` (x + if j<2 then g (j+1) else
0) :: Int
This version runs out of memory. When I scale the numbers down to 1, the
program does run correctly, and takes lots of memory.
Even if I change the seqs into deepseqs, or use BangPatterns (f !i =... ; g !j
= ...), the situation doesn't change.
A monadic version
import Control.Monad.ST.Strict
import Control.Monad
import Data.STRef.Strict
main = print $ runST $ do
s <- newSTRef (0::Int)
let g !i !j =
if (j<=1) then modifySTRef s (+1)>>(g i (j+1)) else return
()
let f !i =
if (i<=1) then g i 1>>(f $ i+1) else return ()
f 1
readSTRef s
also runs out of memory.
So how can I write a program that executes nested loops efficiently?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] simple servers
Hi cafe looking at http://www.haskell.org/haskellwiki/Simple_Servers The last two solutions compared are forkIO vs. explicit event support (based on what was System.Event). Further reading appears to indicate that event support has been integrated into the runtime. Is it true that writing a simple server using forkIO now integrates native event loops implicitly? Or do I still need to create code that explicitly uses (what is now) GHC.Event? One last question. When writing C code, using epoll apis explicitly can impose some blocking. Is the same to be said for GHC.Event? I know all of the changes I am discussing seemed to happen in ghc more than a year ago, sorry, I just can't find anything to explicitly guide me here. Thanks! Brad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to implement nested loops with tail recursion?
I need to implement fast two-level loops, and I am learning using seq to make
calls tail-recursive.
I write programs to compute
main = print $ sum [i*j|i::Int<-[1..2],j::Int<-[1..2]]
This program (compiled with -O2) runs twenty times slower than the unoptimized
(otherwise the loop gets optimized out) C version.
But it seems to run in constant memory, so I assume that it has been turned
into loops.
#include
int main(){
int s=0;
for(int i=1;i<=2;++i){
for(int j=1;j<=2;++j){
s+=i*j;
}
}
printf("%d\n",s);
return 0;
}
Then I write
main = print $ f 1 where
f i = let x = g 1 in x `seq` (x + if i<2 then f (i+1) else 0) ::
Int where
g j = let x = i*j in x `seq` (x + if j<2 then g (j+1) else
0) :: Int
This version runs out of memory. When I scale the numbers down to 1, the
program does run correctly, and takes lots of memory.
Even if I change the seqs into deepseqs, or use BangPatterns (f !i =... ; g !j
= ...), the situation doesn't change.
A monadic version
import Control.Monad.ST.Strict
import Control.Monad
import Data.STRef.Strict
main = print $ runST $ do
s <- newSTRef (0::Int)
let g !i !j =
if (j<=1) then modifySTRef s (+1)>>(g i (j+1)) else return
()
let f !i =
if (i<=1) then g i 1>>(f $ i+1) else return ()
f 1
readSTRef s
also runs out of memory.
So how can I write a program that executes nested loops efficiently?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial statical linking
On Wed, Sep 19, 2012 at 7:06 AM, Jason Dusek wrote: > What I attempted was building a binary with only some C libraries > statically linked, with this command line: > > # Build https://github.com/erudify/sssp on Ubunut 12.04 > ghc -outputdir ./tmp -v --make -O2 sssp.hs -o sssp.ubuntu \ > /usr/lib/x86_64-linux-gnu/libffi.a \ > /usr/lib/x86_64-linux-gnu/libgmp.a \ > /usr/lib/x86_64-linux-gnu/libz.a > > However, this really made no difference. Running `ldd' on the > resulting binary reveals that libz and friends are still > dynamically linked: > On Linux you probably need -optl--whole-archive for this to do anything; alternately, you would need to get the final ld command line out of ghc and insert the above libraries into it *after* the package .a files. Putting them before the packages (including the GHC runtime) that need them, as will happen by default, will cause them to be ignored because they contain no required symbols *at that point* in the link. --whole-archive tells to blindly link the whole static archive in instead of ignoring it. -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial statical linking
2012/9/19 Christian Maeder : > I usually just copy those .a files (that should be linked statically) into > `ghc --print-libdir`. Wow, it worked! But this isn't the sort of change I'd to a user's system that I'd like to encode in a Makefile... -- Jason Dusek pgp // solidsnack // C1EBC57DC55144F35460C8DF1FD4C6C1FED18A2B ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial statical linking
Hi, I usually just copy those .a files (that should be linked statically) into `ghc --print-libdir`. HTH Christian Am 19.09.2012 13:06, schrieb Jason Dusek: 2011/12/1 Irene Knapp : The typical trick to force GHC to statically link a C library is to give the full path to the .a of it as one of the object files in the GHC invocation that does the final linking. This means you don't need any -l or -L flags pertaining to that library. Some libraries are very particular about the order you list them in when doing this, but I don't really understand the issues there. You usually will also have to chase dependencies by hand and list them in the same fashion. I recently tried using this method to create static binary; but I was not able to get it to work. I thought I would revive this old thread and see if anyone else has given it a shot. What I attempted was building a binary with only some C libraries statically linked, with this command line: # Build https://github.com/erudify/sssp on Ubunut 12.04 ghc -outputdir ./tmp -v --make -O2 sssp.hs -o sssp.ubuntu \ /usr/lib/x86_64-linux-gnu/libffi.a \ /usr/lib/x86_64-linux-gnu/libgmp.a \ /usr/lib/x86_64-linux-gnu/libz.a However, this really made no difference. Running `ldd' on the resulting binary reveals that libz and friends are still dynamically linked: ldd sssp.ubuntu linux-vdso.so.1 => (0x7fff94253000) libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x7f0ddfdbb000) libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x7f0ddfb9e000) libgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x7f0ddf92f000) libffi.so.6 => /usr/lib/x86_64-linux-gnu/libffi.so.6 (0x7f0ddf727000) libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x7f0ddf42d000) librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x7f0ddf224000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x7f0ddf02) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x7f0ddec63000) /lib64/ld-linux-x86-64.so.2 (0x7f0ddffdb000) There is always -optl-static which, nowadays, results in a truly static executable; but it leads to a lot of warnings, too. -- Jason Dusek pgp // solidsnack // C1EBC57DC55144F35460C8DF1FD4C6C1FED18A2B ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial statical linking
2011/12/1 Irene Knapp : > The typical trick to force GHC to statically link a C library > is to give the full path to the .a of it as one of the object > files in the GHC invocation that does the final linking. This > means you don't need any -l or -L flags pertaining to that > library. Some libraries are very particular about the order > you list them in when doing this, but I don't really > understand the issues there. You usually will also have to > chase dependencies by hand and list them in the same fashion. I recently tried using this method to create static binary; but I was not able to get it to work. I thought I would revive this old thread and see if anyone else has given it a shot. What I attempted was building a binary with only some C libraries statically linked, with this command line: # Build https://github.com/erudify/sssp on Ubunut 12.04 ghc -outputdir ./tmp -v --make -O2 sssp.hs -o sssp.ubuntu \ /usr/lib/x86_64-linux-gnu/libffi.a \ /usr/lib/x86_64-linux-gnu/libgmp.a \ /usr/lib/x86_64-linux-gnu/libz.a However, this really made no difference. Running `ldd' on the resulting binary reveals that libz and friends are still dynamically linked: ldd sssp.ubuntu linux-vdso.so.1 => (0x7fff94253000) libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x7f0ddfdbb000) libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x7f0ddfb9e000) libgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x7f0ddf92f000) libffi.so.6 => /usr/lib/x86_64-linux-gnu/libffi.so.6 (0x7f0ddf727000) libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x7f0ddf42d000) librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x7f0ddf224000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x7f0ddf02) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x7f0ddec63000) /lib64/ld-linux-x86-64.so.2 (0x7f0ddffdb000) There is always -optl-static which, nowadays, results in a truly static executable; but it leads to a lot of warnings, too. -- Jason Dusek pgp // solidsnack // C1EBC57DC55144F35460C8DF1FD4C6C1FED18A2B ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: som-1.0
Do you have some data that you'd like to understand better? I'm happy to announce a new package called som that may help: http://hackage.haskell.org/package/som https://github.com/mhwombat/som/wiki (wiki) A Kohonen Self-organising Map (SOM) maps input patterns onto a regular grid (usually two-dimensional) where each node in the grid is a model of the input data, and does so using a method which ensures that any topological relationships within the input data are also represented in the grid. This implementation supports the use of non-numeric patterns. In layman's terms, a SOM can be useful when you want to discover the underlying structure of some data. I have a brief tutorial in the wiki, which I hope to expand over the next few weeks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: grid-2.0
I'm happy to announce a new major release of the grid package: http://hackage.haskell.org/package/grid https://github.com/mhwombat/grid/wiki (wiki) WHAT'S NEW: The GridMap module provides ordered maps from tiles on a grid to values. This module is a wrapper around Grid and Map, in order to combine the functionality of grids and maps into a single type. This may be of interest to anyone developing a game based on a grid. ABOUT GRID: Grid provides tools for working with regular arrangements of tiles, such as might be used in a board game or self-organising map (SOM). Grid currently supports triangular, square, and hexagonal tiles, with various 2D and toroidal layouts. If you need a tile shape or layout that isn't currently provided, please let me know. See Math.Geometry.Grid for an example of how to use the package. Suggestions for improvement are welcome. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Haskell] Well-Typed and Skills Matter offer Haskell courses in London in October
Hi. > Oops, I hit send too prematurely, sorry for the seeming bluntness (but it is > still a blunt message, can't apologize for that I suppose): No need to apologize. There's a need for informal meetings as much (or even more) as there is for courses and conferences. > Perhaps a monthly informal gathering similarly (self-)organised to Dorkbot > but focussed on Haskell (and other functional languages) is what I'm really > after, but that still requires some organisation time and a venue, neither > of which necessarily come cheap :( There are several informal meetings on Haskell happening throughout the world. I'm personally not living in the London area, but I regularly attend the Munich Haskell meeting (http://www.haskell-munich.de/). Regarding London, I know there's the Haskell Hoodlums meetup (http://www.meetup.com/hoodlums/), and I think there is or was a Haskell User Group as well, but it's currently listed as "not active" on http://www.haskell.org/haskellwiki/User_groups. Perhaps there's a chance to bring it back to life? Cheers, Andres -- Andres Löh, Haskell Consultant Well-Typed LLP, http://www.well-typed.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Haskell] Well-Typed and Skills Matter offer Haskell courses in London in October
Hi list, Oops, I hit send too prematurely, sorry for the seeming bluntness (but it is still a blunt message, can't apologize for that I suppose): On 19/09/12 09:14, Claude Heiland-Allen wrote: On 19/09/12 08:52, Andres Löh wrote: Registration for all these events is open. I hope to see many of you there. (Referring to the October 10th event: http://skillsmatter.com/event/haskell/haskell-exchange-2012 ) Is there an informal hangout without the £225 price-tag ? Perhaps a monthly informal gathering similarly (self-)organised to Dorkbot but focussed on Haskell (and other functional languages) is what I'm really after, but that still requires some organisation time and a venue, neither of which necessarily come cheap :( So, I understand the need to charge, but it seems quite a high fee to me (especially as there don't seem to be concessions for unwaged / students / etc). Cheers, Andres Thanks, sorry if this caused offence. Three cheers if it revives a democratic informal londonhug thing. Claude ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Haskell] Well-Typed and Skills Matter offer Haskell courses in London in October
> Is there an informal hangout without the £225 price-tag Certainly a great idea. I guess there's most likely some informal meeting after the Haskell eXchange. Perhaps Neil Mitchell knows if there are any concrete plans yet? He's been putting together the program for the conference. Cheers, Andres -- Andres Löh, Haskell Consultant Well-Typed LLP, http://www.well-typed.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Haskell] Well-Typed and Skills Matter offer Haskell courses in London in October
On 19/09/12 08:52, Andres Löh wrote: Registration for all these events is open. I hope to see many of you there. Is there an informal hangout without the £225 price-tag Cheers, Andres ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
