June 2011 - Haskell-Cafe

Map Monoid instance (was commutative monoid?)
by Jens Blanck 25 Jun '11

25 Jun '11

I don't think the original question really is about commutativity, but rather the choice of Monoid instance. Not being especially mathematically inclined, every once and a while I > get a little panicked when I notice that, e.g. Data.Map mappend is a > plain left-biased union, and doesn't actually mappend the values of > the map. > As noted in the reply > > So there's a range of possible Monoid instances for each type, > > More for some types than for others. For Maybe there are three: > > * always take the first/left value; > * always take the last/right value; > * or, use a semigroup operation defined on the values. > > The first two options are provided by the First and Last newtypes, and the > third option is provided by the instance for Maybe itself (except that it > spuriously requires a Monoid instance instead of just a semigroup). > > But why does the Map instance of Monoid _not_ mimic the one chosen for Maybe. I claim this causes unnecessary surprises for users (and lifting the Monoid instance seems more useful, but that is harder to substantiate). Jens

3 2

Why aren't there anonymous sum types in Haskell?
by Elliot Stern 25 Jun '11

25 Jun '11

A tuple is basically an anonymous product type. It's convenient to not have to spend the time making a named product type, because product types are so obviously useful. Is there any reason why Haskell doesn't have anonymous sum types? If there isn't some theoretical problem, is there any practical reason why they haven't been implemented? It seems to me that type inference on anonymous sum types would give you a lot of the power that you get from heterogeneous lists. Whenever you use a heterogeneous list, you've essentially got a homogenous list of some sum type. If you don't handle all of the cases of the sum type, then you're going to eventually run into a type error. It seems to me that having type inference on anonymous sums would allow you to safely get the power of a heterogeneous list. Am I missing something here, or is this correct?

13 14

Haskell Logo
by Michael Xavier 25 Jun '11

25 Jun '11

I wondered if anyone knew the legalities of using the haskell logo, in particular, this one: http://media.nokrev.com/junk/haskell-logos/logo1.png on a website, a personal blog in particular. While I am not yet a primarily haskell coder, I'm using it more and more. I find this logo in particular to be quite beautiful and would probably modify it a bit to emphasize the lambda, which has broader application to computer science beyond 1 language. I can't find any information on what the license is for this image. Could anyone offer any advice on this? -- Michael Xavier http://www.michaelxavier.net

2 1

Re: [Haskell-cafe] Iteratee IO examples
by John Lato 25 Jun '11

25 Jun '11

From: Eric Rasmussen <ericrasmussen(a)gmail.com> > > Hi, > > Examples are very helpful to me too -- thank you for sharing. I'm > especially > curious to see if there are any examples that allow you to use or convert > non-iteratee-based functions. I have only just begun reading about > iteratees > and might be missing the point, but it seems like many of the examples so > far rely on explicit recursion or special functions from one of the > iteratee > modules. > You might be interested in the attoparsec-enumerator and attoparsec-iteratee packages, which adapt attoparsec parsers to work with iteratees. They're small, self-contained, and quite readable. Since attoparsec works with partial parses, it's a natural fit for iteratees. Honestly I'm quite dis-satisfied with the current state of code which depends on iteratee/enumerator. It's nearly all written in a very low-level style, i.e. directly writing 'liftI step', or 'case x of Yield -> ...'. This is exactly what I would hope users could avoid, by using the functions in e.g. Data.Iteratee.ListLike. I've recently added more functions to iteratee which greatly reduce the need for this type of code. I don't know about enumerator, but I expect it isn't rich enough since most user code I've seen is pretty low-level. For some other iteratee examples, you can 'darcs get http://www.tiresiaspress.us/haskell/sndfile-enumerators/' and look at the examples directory (or browse online, of course). > > Is there a way to take a simple function (example below) and use an > enumerator to feed it a ByteString from a file, or do you have to write > functions explicitly to work with a given iteratee implementation? > > import qualified Data.ByteString.Char8 as B > sortLines = B.unlines . sort . B.lines > For this case, there's no point to using iteratees at all. Just read the file in directly to a strict bytestring. Since you're sorting, you'll need to see all the lines before results can be returned. If the file is too big to fit into memory, you'd need a more sophisticated algorithm for which you could use iteratees. In the general case, you need to write for a given iteratee implementation, but in many specific cases it's not necessary. If you want to transform each line of a file, for instance (with iteratee): import Data.ByteString.Char8 as B import Data.Iteratee as I import Data.Iteratee.Char import System.IO import Control.Monad.IO.Class transform :: (ByteString -> ByteString) -> FilePath -> Iteratee [ByteString] IO () transform tFunc oFile = do h <- liftIO $ openFile oFile WriteMode joinI $ rigidMapStream tFunc $ I.mapM_ (B.hPutStrLn h) liftIO $ hClose h rewriteFile :: (ByteString -> ByteString) -> FilePath -> FilePath -> IO () rewriteFile tFunc iFile oFile = fileDriver (joinI $ enumLinesBS (transform tFunc oFile)) iFile An unfolding version would be possible too, which would take a parameter tFunc :: (s -> ByteString -> (s, ByteString)) Maybe I'll add these as utilities in the next version of iteratee. John

1 0

Re: [Haskell-cafe] Software patents covered in GHC?
by austin seipp 25 Jun '11

25 Jun '11

*sigh* CC'ing to the rest of haskell-cafe for completeness. I need to change 'reply all' to a default in my email I guess. On Mon, Jun 20, 2011 at 12:19 PM, austin seipp <as(a)hacks.yi.org> wrote: > Hello, > > Realistically, there probably is. Considering everything down to > linked lists are patented by the USPO, I'd be willing to bet (at least > a dollar or two) that there are many patents out there that apply to > the code used in GHC. I don't know if you could say anything different > about *any* nontrivial software, to be quite honest. > > IANAL however, so I won't attempt to claim in what countries these > patents apply, nor could I cite you patent numbers (legalese being > terse and software patents so seemingly open to interpretation > sometimes, it would be hard to narrow down anyway I think.) > > On Mon, Jun 20, 2011 at 12:10 PM, Shakthi Kannan <shakthimaan(a)gmail.com> wrote: >> Hi, >> >> I would like to know if there are any software algorithms used in the >> Glasgow Haskell Compiler that have been patented? If yes, in which >> countries do they apply? >> >> Just curious to know. >> >> SK >> >> -- >> Shakthi Kannan >> http://www.shakthimaan.com >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > > > -- > Regards, > Austin > -- Regards, Austin

3 4

Re: [Haskell-cafe] toSql and fromSql, for Algebraic Data Type
by Daniel Patterson 25 Jun '11

25 Jun '11

(forgot to CC the list) On Jun 24, 2011, at 8:27 PM, Daniel Patterson wrote: > It looks, from looking at the provided instances (not from having done it myself), that you need to define safeConvert functions to and from your value. Here is a partial list of conversions to and from String. > instance Convertible String SqlValue where > safeConvert = return . SqlString > instance Convertible SqlValue String where > safeConvert (SqlString x) = return x > safeConvert (SqlByteString x) = return . BUTF8.toString $ x > safeConvert (SqlInt32 x) = return . show $ x > safeConvert (SqlInt64 x) = return . show $ x > safeConvert (SqlWord32 x) = return . show $ x > safeConvert (SqlWord64 x) = return . show $ x > safeConvert (SqlInteger x) = return . show $ x > safeConvert (SqlChar x) = return [x] > safeConvert (SqlBool x) = return . show $ x > safeConvert (SqlDouble x) = return . show $ x > safeConvert (SqlRational x) = return . show $ x > > On Jun 24, 2011, at 8:02 PM, Tom Murphy wrote: > >> Hi *, >> The title is self-explanatory. I'd like to store information from >> an algebraic data type in an SQL database, but the type signature of >> toSql (toSql >> :: Data.Convertible.Base.Convertible a SqlValue => a -> SqlValue) >> doesn't make sense to me. >> How is this done (how do I make an instance of a typeclass like that?) >> >> Thanks for your time, >> Tom >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

None brute-force BWT algorithm
by larry.liuxinyu 24 Jun '11

24 Jun '11

Hi, I read a previous thread about BWT implementation in Haskell: http://www.mail-archive.com/haskell-cafe@haskell.org/msg25609.html and http://sambangu.blogspot.com/2007/01/burrows-wheeler-transform-in-haskell They are all in a `brute-force' way, that is implement based on Burrows-Wheeler's definition like below: BWT: sort the rotations of input S to get a matrix M', return the last column L, and the row I, where S appears in M' -- O( n^2 \lg n) bwt :: (Ord a)=>[a]->([a], Int) bwt s = (map last m, i) where m = sort [ drop i s ++ take i s | i<-[1..length s]] (Just i) = elemIndex s m And the IBWT: Re-construct M' by iteratively sort on input L, add one column at a time, and pick the I-th row in M' -- O( n^3 \lg n ) ibwt :: (Ord a)=> ([a], Int) -> [a] ibwt (r, i) = m !! i where m = iterate f (replicate n []) !! n f = sort . zipWith (:) r n = length r I read Richard Bird's book, `Pearls of functional algorithm design', there is another solution. Although it is deduced step by step, the core idea is based on random access the list by index. The algorithm mentioned in the book uses suffixes for sorting instead of rotations. The performance are same in terms of big-O. I wrote the following program accordingly. BWT: sort S along with the index to get a new order of IDs, and return a permutation of S based on IDs. -- O( n^2 \lg n) if (!!) takes O(n) time bwt' :: (Ord a)=> [a] -> ([a], Int) bwt' s = (l, i) where l = map (\i->s !! ((i-1) `mod` n)) ids (Just i) = elemIndex 0 ids ids = map snd $ sortBy (compare `on` fst) $ zip rots [0..] rots = init $ zipWith (++) (tails s) (inits s) -- only non-empties n = length s IBWT: Sort the input L along with index to get a Transform vector, T [1], then permute L iteratively on T start from row I. -- O( n^2 ) if (!!) takes O(n) time ibwt' :: (Ord a) => ([a], Int) -> [a] ibwt' (r, i) = fst $ iterate f ([], i) !! n where t = map snd $ sortBy (compare `on` fst) $ zip r [0..] f (s, j) = let j' = t !! j in (s++[r !! j'], j') n = length r However, As I commented, the (!!) takes time proportion to the length of the list, Although it can be turned into real Haskell Array by listArray (0, n-1) xs. I wonder if there are any purely functional implementations of BWT/IBWT, which don't base on random access idea nor in brute-force way. [Reference] [1], Mark Nelson. `Data Compression with the Burrows-Wheeler Transform'. http://marknelson.us/1996/09/01/bwt/ -- Larry, LIU Xinyu https://github.com/liuxinyu95/AlgoXY

2 3

Re: [Haskell-cafe] Category theory as a design tool
by wren ng thornton 24 Jun '11

24 Jun '11

On 6/23/11 4:30 PM, Alexander Solla wrote: > Please read "Fast and Loose Reasoning is Morally Correct". > http://www.comlab.ox.ac.uk/people/jeremy.gibbons/publications/fast+loose.pdf > > As I have told you before, it is perfectly appropriate to ignore > bottom-the-type and bottoms-the-inexpressible proto-values to recover the > categorical product semantics of (,). It's not even hard. It will make > your life easier. All you have to do is apply an equivalence relation that > considers all bottom-proto-values as equivalent. Domain theory is an > unnecessary complication. All bottoms have the same semantics anyway -- > they all diverge. I've read it a few times, even before the first time you suggested it. It's an excellent paper. And yet, there are times when fast and loose reasoning is not factually correct, morals aside. For one, not all bottoms do diverge, thanks to extensible exceptions. The fact that tuples are not products does have real, moral(!) ramifications--- even if we fallaciously assume that all bottoms do diverge. For example, it dictates a particular implementation for Arrow (->), an implementation which can cause performance issues due to excessive laziness. There are plenty of other examples where the choice of implementation is forced by the desire to be lazy, even when the laziness is not necessary or helpful in all contexts. I'm a big fan of laziness, but it's a two edged sword. Forcing people to grip one edge or to write duplicate code for different circumstances is not an agenda I can support. Another example that's near and dear to many folks on this list is the fact that the existence of bottoms means Haskell as a logic is inconsistent and therefore lacks many properties we would like for provably correct programming. Regardless of how we reason about bottom, the fact that we cannot choose to *not* reason about bottom means that the game is already fixed. Clearly you're not interested in the goals of total functional programming, but many people on this list are, and your continuing argument that those goals are irrelevant (or irreconcilable with laziness) is not endearing. Arnaud was asking how CT could be used when designing systems. I gave an example. That you do not like my example is neither here nor there. Besides, domain theory isn't all that complicated; especially not when comparing it to the whole of category theory. -- Live well, ~wren

2 1

ANN: Two new random-fu releases
by James Cook 24 Jun '11

24 Jun '11

Announcing the Hackage release of two new versions[1,2] of the random- fu package: Version 0.1.4 is a build-fix release that extends support of the 0.1 API to GHC 7. Version 0.2 is a significantly restructured version of the package. Its API is mostly the same as the old for end users, but its back-end has been redesigned and separated into two new packages: "random- source" provides an abstract interface for sources of entropy, and "rvar" provides an abstract interface for consumers of entropy. The parts remaining in "random-fu" provide a more concrete interface for representing and sampling specific distributions. -- James [1] http://hackage.haskell.org/package/random-fu-0.1.4 [2] http://hackage.haskell.org/package/random-fu-0.2

1 0

Haskell Weekly News: Issue 187
by Daniel Santa Cruz 24 Jun '11

24 Jun '11

Welcome to issue 187 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of June 12 to 18, 2011. Announcements Ian Lynagh announced a new patchlevel release of GHC (7.0.4). "This release contains a handful of bugfixes relative to 7.0.3, so we recommend upgrading." http://goo.gl/hOvdA Nicolas Wu released the third instance fo Haskell Parallel Digest. Many thanks to Nick and Eric for putting this together. http://goo.gl/s5muy Jeroen Janssen invited us to the 8th Ghent Functional Programming Group Meeting, to be held on Thursday, the 30th of June, in the Technicum building of Ghent University. http://goo.gl/G081Q Quotes of the Week * monochrom: if I were dying to learn covariance, I would not be looking for entertainment, like, I'm dying, I only have 5 minutes to learn covariance, thank you very much * hpc: the categorical dual of a hippomorphism should be a giraffomorphism * ksf: but, as, maybe indeed or not apparently, english, in, or especially in, punctuation matters is an utter mess. * 00:56:03 <benmachine> @faq can haskell tell if I am lagging [...] 00:57:18 <lambdabot> The answer is: Yes! Haskell can do that. Top Reddit Stories * Haskell: the Craft of Functional Programming, 3rd edition is out! Domain: haskellcraft.com, Score: 44, Comments: 10 On Reddit: http://goo.gl/6ZInj Original: http://goo.gl/t0GAX * GHC 7.0.4 is out Domain: haskell.org, Score: 42, Comments: 2 On Reddit: http://goo.gl/oxSJH Original: http://goo.gl/EzWUP * SafeHaskell pushed into GHC Domain: haskell.org, Score: 39, Comments: 5 On Reddit: http://goo.gl/sOrjr Original: http://goo.gl/2Rw56 * Minimum footprint for a GHC program: or, think about your TSOs Domain: stackoverflow.com, Score: 23, Comments: 0 On Reddit: http://goo.gl/eIF0o Original: http://goo.gl/dRgLG * Pieces of Yesod: Inverting a Haskell Function Domain: chplib.wordpress.com, Score: 21, Comments: 8 On Reddit: http://goo.gl/NFJNH Original: http://goo.gl/x2cz2 * The 2011 ICFP contest is starting in just 6 hours! Domain: icfpcontest.org, Score: 20, Comments: 15 On Reddit: http://goo.gl/BS7XI Original: http://goo.gl/oqj0Y * A pattern for avoiding allocation : Inside T5 Domain: blog.ezyang.com, Score: 19, Comments: 12 On Reddit: http://goo.gl/thuRP Original: http://goo.gl/IZCIh * Package of the Day: an improved runghc for fast repeated runs Domain: hackage.haskell.org, Score: 16, Comments: 9 On Reddit: http://goo.gl/k6mQK Original: http://goo.gl/a0DAC * The Supero Supercompiler Domain: community.haskell.org, Score: 16, Comments: 2 On Reddit: http://goo.gl/vBeFO Original: http://goo.gl/3QsmC * Galois Video: Building an Open-Source Autonomous Quad-Copter Domain: corp.galois.com, Score: 15, Comments: 3 On Reddit: http://goo.gl/HZghO Original: http://goo.gl/6AcMw Top StackOverflow Questions * Why does performGC fail to release all memory? votes: 17, answers: 2 Read on SO: http://goo.gl/dRgLG * OSX, ghci, dylib, what is the correct way? votes: 17, answers: 1 Read on SO: http://goo.gl/0s9Tu * Why does Haskell's `head` crash on an empty list (or why *doesn't* it return an empty list)? (Language philosophy) votes: 15, answers: 6 Read on SO: http://goo.gl/tghQR * Towards understanding CodeGen* in the Haskell LLVM bindings votes: 13, answers: 1 Read on SO: http://goo.gl/LPZ2F * What happens to you if you break the monad laws? votes: 13, answers: 3 Read on SO: http://goo.gl/Trvny * Is anyone using delimited continuations to do web development in Haskell? votes: 12, answers: 3 Read on SO: http://goo.gl/hGjuB * The concept of Bottom in Haskell votes: 12, answers: 1 Read on SO: http://goo.gl/9b1ZJ About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz

11 12