Re: [Haskell-cafe] Most used functions in hackage
Hi Dmitry, Thanks for the links. I've been through the 24 Days of Hackage, but I think its time to run through them again now that I'm a little more familiar with everything. Why do you think browsing function by function is a bad idea? It seems that knowing exactly what the most used functions are would be an extremely effective way of finding both which parts of the Prelude and Hackage are most broadly useful (instead of browsing them like a phonebook) and also finding support from the community as the most commonly used functions would likely be the easiest to find support for. I guess what I'm looking for doesn't exist, which is what it is. I'm just interested in why it's not an ideal way to take in Haskell, starting with the common and moving to the to rare. Thanks, Casey On Mon, Jan 28, 2013 at 11:57 PM, Dmitry Vyal akam...@gmail.com wrote: On 01/29/2013 11:21 AM, Casey Basichis wrote: Is there any link that counts the use of all functions in all packages in Hackage and lists them by frequency or by other stats? I'm still new to haskell but I've been working my way through tons and tons of tutorials and books. It would be very helpful to target in on the current reality of the most critical functions. Hello Casey, You can use Hoogle http://www.haskell.org/hoogle/ to get information about a particular function or to find a function by a part of it's signature. While it's helpful to carefully study some basic modules like Prelude function by function, I don't think it's a good approach in general. I suggest you to look for reviews of popular modules. Personally, I found 24 days of hackage http://ocharles.org.uk/blog/ to be quite informative. I wouldn't argue it's a best source for a beginner, but at least it gives quite a broad perspective. Best regards, Dmitry -- Casey James Basichis Composer - Cartoon Network http://www.caseyjamesbasichis.com caseybasic...@gmail.com 310.387.7540 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] list comprehansion performance has hug different
Hi Cafe, I have two programs for the same problem Eight queens problem, the link is http://www.haskell.org/haskellwiki/99_questions/90_to_94. My two grograms only has little difference, but the performance, this is my solution: -- solution 1 queens1 :: Int - [[Int]] queens1 n = map reverse $ queens' n where queens' 0 = [[]] queens' k = [q:qs | q - [1..n], qs - queens' (k-1), isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (λ(colDist, q) - abs (try - q) == colDist) $ zip [1..] qs -- solution 2-- queens2 :: Int - [[Int]] queens2 n = map reverse $ queens' n where queens' 0 = [[]] queens' k = [q:qs | qs - queens' (k-1), q - [1..n], isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (λ(colDist,q) - abs (try - q) == colDist) $ zip [1..] qs the performance difference is: (set :set +s in ghci) *Main length (queens1 8) 92 (287.85 secs, 66177031160 bytes) *Main length (queens2 8) 92 (0.07 secs, 17047968 bytes) *Main The only different in the two program is in the first is q - [1..n], qs - queens' (k-1), and the second is qs - queens' (k-1), q - [1..n]. Does sequence in list comprehansion matter? And why? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:25:49 +0300: The only different in the two program is in the first is q - [1..n], qs - queens' (k-1), and the second is qs - queens' (k-1), q - [1..n]. In the first case `queens' (k-1)` is being recomputed for every q (that is, n times). Of course it would matter :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
Hi Artyom, Thanks! But I don't understand why in the first case queens' (k-1) is being recomputed n times? On Tue, Jan 29, 2013 at 5:31 PM, Artyom Kazak artyom.ka...@gmail.comwrote: Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:25:49 +0300: The only different in the two program is in the first is q - [1..n], qs - queens' (k-1), and the second is qs - queens' (k-1), q - [1..n]. In the first case `queens' (k-1)` is being recomputed for every q (that is, n times). Of course it would matter :) __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:40:08 +0300: Hi Artyom, Thanks! But I don't understand why in the first case queens' (k-1) is being recomputed n times? Because your list comprehension is just a syntactic sugar for concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) (queens' (k-1))) [1..n] Here `queens' (k-1)` does not depend on `qs`, and therefore it *could* be floated out of the lambda: let queens = queens' (k-1) in concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) queens) [1..n] But it is an unsafe optimisation. Suppose that the `queens` list is very big. If we apply this optimisation, it will be retained in memory during the whole evaluation, which may be not desirable. That’s why GHC leaves this to you. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
Thanks again! I understand now. I'll be careful when the next time I use list comprehension. On Tue, Jan 29, 2013 at 5:48 PM, Artyom Kazak artyom.ka...@gmail.comwrote: Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:40:08 +0300: Hi Artyom, Thanks! But I don't understand why in the first case queens' (k-1) is being recomputed n times? Because your list comprehension is just a syntactic sugar for concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) (queens' (k-1))) [1..n] Here `queens' (k-1)` does not depend on `qs`, and therefore it *could* be floated out of the lambda: let queens = queens' (k-1) in concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) queens) [1..n] But it is an unsafe optimisation. Suppose that the `queens` list is very big. If we apply this optimisation, it will be retained in memory during the whole evaluation, which may be not desirable. That's why GHC leaves this to you. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
So this is a problem in lazy evaluation language, it will not appear in python or erlang, am i right? On Tue, Jan 29, 2013 at 5:54 PM, Junior White efi...@gmail.com wrote: Thanks again! I understand now. I'll be careful when the next time I use list comprehension. On Tue, Jan 29, 2013 at 5:48 PM, Artyom Kazak artyom.ka...@gmail.comwrote: Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:40:08 +0300: Hi Artyom, Thanks! But I don't understand why in the first case queens' (k-1) is being recomputed n times? Because your list comprehension is just a syntactic sugar for concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) (queens' (k-1))) [1..n] Here `queens' (k-1)` does not depend on `qs`, and therefore it *could* be floated out of the lambda: let queens = queens' (k-1) in concatMap (\q - concatMap (\qs - if isSafe q qs then [q:qs] else []) queens) [1..n] But it is an unsafe optimisation. Suppose that the `queens` list is very big. If we apply this optimisation, it will be retained in memory during the whole evaluation, which may be not desirable. That's why GHC leaves this to you. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Most used functions in hackage
On Tue, 29 Jan 2013 09:23:34 +0100, Casey Basichis caseybasic...@gmail.com wrote: I guess what I'm looking for doesn't exist, which is what it is. I'm just interested in why it's not an ideal way to take in Haskell, starting with the common and moving to the to rare. It is worth while to study the Prelude functions: A Tour of the Haskell Prelude http://undergraduate.csse.uwa.edu.au/units/CITS1211/Documentation/tourofprelude.html and: A tour of the Haskell Monad functions http://members.chello.nl/hjgtuyl/tourdemonad.html Regards, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html Haskell programming -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
Junior White efi...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 12:59:31 +0300: So this is a problem in lazy evaluation language, it will not appear in python or erlang, am i right? Not quite. Compilers of imperative languages don’t perform CSE (common subexpression elimination) either; `queens' (k-1)` could have some side effects, after all, and performing a side effect only once instead of n times is a definite bug. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] quotRem and divMod
On Tuesday 29 January 2013, 03:27:41, Artyom Kazak wrote: Hi! I’ve always thought that `quotRem` is faster than `quot` + `rem`, since both `quot` and `rem` are just wrappers that compute both the quotient and the remainder and then just throw one out. However, today I looked into the implementation of `quotRem` for `Int32` and found out that it’s not true: quotRem x@(I32# x#) y@(I32# y#) | y == 0 = divZeroError | x == minBound y == (-1) = overflowError | otherwise = (I32# (narrow32Int# (x# `quotInt#` y#)), I32# (narrow32Int# (x# `remInt#` y#))) Why? The `DIV` instruction computes both, doesn’t it? And yet it’s being performed twice here. Couldn’t one of the experts clarify this bit? It's not necessarily performed twice. func a b = case a `quotRem` b of (q, r) - q+r produces idivq 8(%rbp) movq %rax,%rbx movq $GHC.Int.I32#_con_info,-8(%r12) movslq %edx,%rax movslq %ebx,%rbx addq %rax,%rbx as the relevant part of the assembly, with only one idivq instruction. I don't know whether you can rely on the code generator emitting only one division instruction in all cases, but in simple cases, it does (on x86_64, at least). Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] quotRem and divMod
Shachaf Ben-Kiki shac...@gmail.com писал(а) в своём письме Tue, 29 Jan 2013 09:09:37 +0300: That code is from base 4.5. Here's base 4.6: quotRem x@(I32# x#) y@(I32# y#) | y == 0 = divZeroError -- Note [Order of tests] | y == (-1) x == minBound = (overflowError, 0) | otherwise = case x# `quotRemInt#` y# of (# q, r #) - (I32# (narrow32Int# q), I32# (narrow32Int# r)) So it looks like it was improved in GHC 7.6. In particular, by this commit: http://www.haskell.org/pipermail/cvs-libraries/2012-February/014880.html Shacha Well, I’m glad to know that it has been fixed in the newer GHC (I’m still on 7.4). Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] catamorphisms and attribute grammars
On Sun, Jan 27, 2013 at 12:20:25AM +, Roman Cheplyaka wrote:
Very nice! This can be generalized to arbitrary arrows:
{-# LANGUAGE ExistentialQuantification #-}
import Prelude hiding (id)
import Control.Arrow
import Control.Applicative
import Control.Category
data F from to b c = forall d . F (from b d) (to d c)
instance (Arrow from, Arrow to) = Functor (F from to b) where
fmap f x = pure f * x
instance (Arrow from, Arrow to) = Applicative (F from to b) where
pure x = F (arr $ const x) id
F from1 to1 * F from2 to2 =
F (from1 from2) (to1 *** to2 arr (uncurry id))
You only require that from b is Applicative, so that in turn can be
generalized:
data F g to c = forall d . F (g d) (to d c)
instance (Applicative g, Arrow to) = Functor (F g to) where
fmap f x = pure f * x
instance (Applicative g, Arrow to) = Applicative (F g to) where
pure x = F (pure x) id
F from1 to1 * F from2 to2 =
F ((,) $ from1 * from2) (to1 *** to2 arr (uncurry id))
I wonder what's a categorical interpretation of F itself.
It's a variety of left Kan extension (cf section 5 of Constructing
Applicative Functors at MPC'2012).
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type classes, collections, sum types, closures, and a massive headache
Today I thought it was about time to simplify how new 'things' of a certain
kind are added to the system. These things are some a cross between an event
and an assertion of a fact in a rule based system. There are many different
kinds of these things. I already have more than a dozen commonplace ones, and
I expect there's a much larger number of more specialized ones that a user
will want to add on their own. While they start out quite differently, they
end up satisfying a common interface and follow the identical three or four
state lifecycle. This sounded like a type class to me, and in fact, easily
implemented as such.
I hardly ever use typeclasses, I've never used existential types or
GADTs, and it's worked fine for me for many years. Maybe just a
difference in programming style, or the sorts of things I write, but
implies at least that you can get very far not using any of that
stuff.
If each of your things have the same 3 or 4 states, can you make a
state into a value, and compose them? E.g. 'thing1 = state1 state2
thing1state where thing1state = ...' and state1 and state2 are
defined in a library.
If you have lots of different ways to take A to B and want to let the
caller configure it, then just pass an A-B function. If you want to
configure an unpredictable subset of things, then maybe make a default
record and pass 'default { aToB = customVersion }'. If each function
depends on a configuration environment that you want to inherit from
callers, then maybe put that record into a Reader.
In my case, the main design decision winds up being the balance of
data (i.e. records with values or functions) and code (i.e. functions
that do parts of what you want and can be composed together in various
ways). Code is extensible and flexible but can't be manipulated, data
is inflexible (in that you have to hardcode some kind of schema),
but that means you can write functions to transform it.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Uniplate and rewriting with different types
Hi Chris, With the following type, and transformation functions: data Odd = OddOne Even | OddZero Even deriving (Data,Typeable,Show) data Even = EvenOne Odd | EvenZero Odd | Nil deriving (Data,Typeable,Show) t1,t2,t3 :: Even - Maybe Even But if one of the transformations has a different type, you can't do it this way. For instance, redefine t2 to have a different type: t2 :: Odd - Maybe Odd t2 (OddZero (EvenOne x)) = Just $ OddZero (EvenZero x) t2 x = Nothing and you are stuck because the functions of different types can't be combined into a single transformation. My question is: is there a good way to combine the transformation functions if they have different types? Currently, no. Although there is something definitely related, with transformBis: http://hackage.haskell.org/packages/archive/uniplate/1.6.10/doc/html/Data-Generics-Uniplate-Data.html#v:transformBis That takes a list of transformation functions of different types and acts as though you did transform on each one in turn. You could certainly imagine adding rewriteBis in the same style, and with your version you almost have. The transformBis function is particularly efficient because it knows which traversals or parts of traversals can be fused without changing the semantics. rewriteBis could certainly do the same trick. If you provided a patch for rewriteBis I'd certainly apply it! Thanks, Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Heads up: planned removal of String instances from HTTP package
Hi, tl;dr: I'm planning on removing the String instances from the HTTP package. This is likely to break code. Obviously it will involve a major version bump. The basic reason is that this instance is rather broken in itself. A String ought to represent Unicode data, but the HTTP wire format is bytes, and HTTP makes no attempt to handle encoding. This was discussed on the libraries@ list a while back, but I'm happy to discuss further if there's a general feeling that this is a bad thing to do: http://www.haskell.org/pipermail/libraries/2012-September/018426.html I will probably upload the new version in a week or two. Cheers, Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Heads up: planned removal of String instances from HTTP package
On Tue, Jan 29, 2013 at 2:15 PM, Ganesh Sittampalam gan...@earth.li wrote: tl;dr: I'm planning on removing the String instances from the HTTP package. This is likely to break code. Obviously it will involve a major version bump. The basic reason is that this instance is rather broken in itself. A String ought to represent Unicode data, but the HTTP wire format is bytes, and HTTP makes no attempt to handle encoding. This was discussed on the libraries@ list a while back, but I'm happy to discuss further if there's a general feeling that this is a bad thing to do: http://www.haskell.org/pipermail/libraries/2012-September/018426.html I will probably upload the new version in a week or two. I think it's the right thing to do. Providing a little upgrade guide should help things to go smoother. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Handling exceptions or gracefully releasing resources
`Control.Exception.bracket` is a nice function to acquire and release a resource in a small context. But, how should I handle resources that are hold for a long time? Should I put `Control.Exception.finally` on every single line of my finalizers? What exceptions may occur on an IO operation? Every IO function has the risk of throwing an exception? Thanks, Thiago. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Handling exceptions or gracefully releasing resources
Hi, The pattern is essentially the same as in imperative languages; every allocation should involve a finally clause that deallocates the resource. On Tue, Jan 29, 2013 at 2:59 PM, Thiago Negri evoh...@gmail.com wrote: Should I put `Control.Exception.finally` on every single line of my finalizers? I'm not sure what you're asking here. If your finally clause tries to call close, you don't have to catch exceptions raise by close (what would you do with them anyway). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
On 29/01/2013, at 10:59 PM, Junior White wrote:
So this is a problem in lazy evaluation language, it will not appear in
python or erlang, am i right?
Wrong. Let's take Erlang:
[f(X, Y) || X - g(), Y - h()]
Does the order of the generators matter here?
You _bet_ it does.
First off, in all of these languages, it affects
the order of the results. Let's take a toy case:
g() - [1,2].
h() - [a,b]. % constants
f(X, Y) - {X,Y}. % a pair
[f(X, Y) || X - g(), Y - h()]
yields [{1,a},{1,b},{2,a},{2,b}]
[f(X, Y) || Y - h(), X - g()]
yields [{1,a},{2,a},{1,b},{2,b}]
Now let's change it by giving g/0 and h/0 (benign) side effects.
g() - io:write('g called'), io:nl(), [1,2].
h() - io:write('h called'), io:nl(), [a,b].
Generating X before Y yields
'g called'
'h called'
'h called'
[{1,a},{1,b},{2,a},{2,b}]
Generating Y before X yields
'h called'
'g called'
'g called'
[{1,a},{2,a},{1,b},{2,b}]
If a function call may yield side effects, then the compiler
must not re-order or coalesce calls to that function.
This applies to both Erlang and Python (and to SETL, which
had set and tuple comprehensions before Erlang, Python, or
Haskell were conceived).
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] list comprehansion performance has hug different
On 1/29/13 4:25 AM, Junior White wrote: Hi Cafe, I have two programs for the same problem Eight queens problem, the link is http://www.haskell.org/haskellwiki/99_questions/90_to_94. My two grograms only has little difference, but the performance, this is my solution: The difference is what's called dynamic programming (an utterly non-intuitive an un-insightful name). When we have the program: [ f x xs | xs - g, x - h ] we're saying, first get me a partial solution (xs), and then try every possible way of extending that to a larger solution (x). It should be obvious from this description that the computation of each partial solution xs will be shared among all candidates x, but that the computation of x will not be shared between each xs. On the other hand, when we have the program: [ f x xs | x - h, xs - g ] we're saying, first get me all ways to start a solution (x), and then try to solve the rest of the problem (xs). It should be obvious from this description that the computation of each x will be shared, but the computation of each xs will not. Imperatively, this is exactly the same distinction as between the following programs: for xs in g: for x in h: yield f(x,xs) for x in h: for xs in g: yield f(x,xs) This difference in sharing can, as you've seen, cause huge differences in runtime. Usually it's the difference between a polytime algorithm and some exptime algorithm. To see why, just think about the call graph. It may be more helpful here to think about something like Fibbonaci numbers. In the memoizing version, you're storing the work from solving smaller problems and sharing that among the different ways of extending the solution; whereas in the naive version, you're recomputing the same thing over and over. The call graph for the former is a DAG (or more generally, a packed forest) whereas the call graph for the latter is the tree you get by unfurling all the shared structure in the DAG. This distinction has nothing whatsoever to do with Haskell, and has everything to do with Intro Algorithms. Loop ordering matters in every language with loops, from Haskell to C to Python to Prolog. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Heads up: planned removal of String instances from HTTP package
On 29/01/2013 22:46, Johan Tibell wrote: On Tue, Jan 29, 2013 at 2:15 PM, Ganesh Sittampalam gan...@earth.li wrote: tl;dr: I'm planning on removing the String instances from the HTTP package. This is likely to break code. Obviously it will involve a major version bump. I think it's the right thing to do. Providing a little upgrade guide should help things to go smoother. One obvious cheap-and-dirty migration is via a newtype wrapper for String that embeds the old broken behaviour (char8 encoding). Perhaps the package should provide that? (with appropriate warnings etc) Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
