- Haskell-Cafe - Haskell.org

commutative monoid?
by Evan Laforge 25 Jun '11

25 Jun '11

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. Then I remember that monoids are associative, not commutative, and it's totally allowed to do that. Even if you mappend the values, the result is only as commutative as the monoid instance for the values. But clearly you can make that choice. For instance, Maybe's Monoid wants to mappend the elements. This is always a little disconcerting to me because the MonadPlus instance for Maybe doesn't do that. So there's a range of possible Monoid instances for each type, and maybe they were chosen by historical happenstance rather than some kind of "principle monoid" (is there such a thing?). Is there a name for the thing that's like a monoid, but the operator is commutative too? That would narrow down the implementation choices, e.g. Data.Map would have to combine the values. So it seems like if your operation is commutative, you can put it in "c-monoid" and not rely so much on the happenstance of the instances, since they are more constrained. And of course you are then free to reorder things, which is a nice bit of flexibility. So is there a typeclass for that? This article is about the mathematical concept. For the alien creatures in the Doctor Who adventure, see The Ark (Doctor Who). I guess I never saw that episode... but it sounds like they're closer to warm fuzzies than the slimy sleeping bag monster I imagined.

2 1

ANNOUNCE: Win32-junction-point-0.0.1
by Michael Steele 25 Jun '11

25 Jun '11

I'm pleased to announce the initial release of Win32-junction-point * hackage: http://hackage.haskell.org/package/Win32-junction-point * git repository: https://github.com/mikesteele81/Win32-junction-point This package provides the ability to manipulate NTFS junction points as supported by Windows 2000 and above. Junction points, along with NTFS hard links and NTFS symbolic links, are a type of symbolic link that can be made between folders existing on the same filesystem. Please read Microsoft KB205524 [1] for more information on junction points. Junction points have always been left undocumented in the Win32 SDK. The Windows 2000 Resource Kit came with a command-line utility named linkd.exe to work with them. Later, Mark Russinovich of SysInternals distributed a replacement utility named Junction [2] which accomplished the same thing. This source code is based on an article [3] and C++ library [4] written by Mike Nordell at codeproject.com. It is against Microsoft's recommendation to make use of undocumented API features. Use this library at your own risk. [1] http://support.microsoft.com/?kbid=205524 [2] http://technet.microsoft.com/en-us/sysinternals/bb896768 [3] http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=194 [4] http://www.codeproject.com/KB/winsdk/junctionpoints.aspx -- Michael Steele

1 0

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