News aggregator

HTTP/2 implementation?

haskell-cafe - Sun, 07/20/2014 - 8:11pm
Has anyone started a HTTP/2 implementation in Haskell? I see there's a HPACK-08 Haskell implementation, but I haven't seen an actual HTTP/2 impl. I've been looking at starting some work on this and didn't want to replicate effort elsewhere that I may have missed. Cheers, Ben _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Douglas M. Auclair (geophf): That's totes my Bag!

Planet Haskell - Sun, 07/20/2014 - 7:14pm
So, does that mean I like tote-bags?

So, today's question on @1HaskellADay was this:

write a function countOccurences :: [Stirng] -> Map Char Int

(typos faithfully reproduced)

such that


lookup 'l' $ countOccurences "Hello" ~> Just 2
lookup 'q' $ countOccurences "Hello" ~> Nothing


Okay, that can be done easily enough, I suppose, by torquing Map into something that it isn't, so one gets wrapped around the axel of creating a mapping from characters to occurrences.

But why?

First of all, countOccurences maps a String (not a List of Strings) to a Map, and that map is a very specialized kind of map that has existed in the literature for quite a while, and that map is known as the Bag data type, and is also, nowadays, called the MultiSet by people too embarrassed to say the word 'bag' in a sentence, because of their prior drug convictions.

("I got two months for selling a dime bag.")

So they now twist the word 'Set' (a 'collection of unique objects') to mean something that's not a set at all, the 'Multi'Set, which is a 'collection of unique objects, but you can have multiples of these unique objects, so they're not unique at all, so it isn't a set at all, but we need to say the word 'set' because we can't say the word 'bag' because saying the word 'bag' would make us sound plebeian for some reason.'

Yeah, that. 'MultiSet.'

What. Ev. Er.

But I digress.

As always.

So I COULD write the countOccurences as a String -> Map Char Int function, but then: why bother? You can either write tons of algorithmic code that obscures the intent or just simply use the appropriate data type.

I went for the latter.

Now, I wuz gonna do a dependently-typed pair to represent an occurrence...

... notice how countOccurences is so badly misspelled, by the way?

SOMEbody didn't QA-check their problem for the day today, I'm thinking.

... but then I said: 'eh!'

I mean: WHY is lookup 'q' $ countOccurences "Hello" ~> Nothing?

WHY can't it be that count 'q' for a Bag Char representation of "Hello" be 0? 0 is a valid answer and it keeps everything nice and monoidal without having to lift everything unnecessarily into the monadic domain.

So, yeah. Let's do that, instead.

So, here we go, and in Idris, because that's how I'm rolling these days. The advantages of dependent types have been enumerated elsewhere, so we'll just go with that they're better as an assumption and move on, using them, instead of extolling them, in this post.

Wrong!

So, my first attempt at Bag crashed and burned, because I did this:



data Bag : (x : Type) -> Type where
    add : Bag x -> x -> Bag x
    emptyBag : Bag x



and the compiler was fine with that. Hey, I can declare any type I'd like, so long as the types just stay as types, but as soon as I tried to define these things:



emptyList : List x
emptyList = []

emptyBag = Bag emptyList
add (Bag []) x = Bag [(x, 1)]
add (Bag ((x, y) :: rest)) x = Bag ((x, y + 1) :: rest)
add (Bag ((z, y) :: rest)) x = Bag ((z, y) :: (add rest x))



The compiler looked at me and asked: 'geophf, what in tarnation are you-ah tryin' to do?'

And about the only intelligent answer I could muster was: 'Ummmm... idk.'

I had gotten too clever for myself by half, trying to reshape a data type you learn in Comp.Sci. 101 as a purely functional type.

Back to Basics ... (but not BASIC)

So, let's just declare Bag to be what it is and KISS: 'keep it simple, stupid!'

Yes, let's.

data Bag x = Air | Stuffed (x, Nat) (Bag x)

Now, I so totally could've gone with the balanced binary-tree representation instead of the simple and standard linked list, but, you know: 'live and learn!'

With this declaration the emptyBag becomes so trivial as to be unnecessary, and then add is simplicity, itself, too, but add is, either way, so that's not saying much.

add : Eq x => Bag x -> x -> Bag x
add Air x = Stuffed (x, 1) Air
add (Stuffed (z, y) rest) x =
    case x == z of
        True  => Stuffed (x, y + 1) rest
        False => Stuffed (z, y) (add rest x)

Now, you see me relying on the case-statement, here. Unhappily.

I'd like my dependent types to say, 'unify x with x (reflexive) for the isomorphic case, and don't unify x with z for the other case.' But we're not there yet, or my coding isn't on par with being there yet, so I forced total coverage bifurcating the result-set into isomorphic and not with a hard-case statement.

Ick. I hate explicit case-statements! Where is really, really, really smart pattern-matching when I need it?

But with add, constructing a Bag becomes easy, and then counting elements of that bag is easy, too (again, with another case-statement, sigh!):


count : Eq x => x -> Bag x -> Nat
count _ Air = 0
count x (Stuffed (z, y) rest) =
    case x == z of
        True  => y
        False => count x rest


countOccurences (with one-too-few 'r's in the function name) becomes easy, given the Bag data type:

countOccurences : String -> Bag Char
countOccurences str = co' (unpack str) where
    co' [] = Air
    co' (char :: rest) = add (co' rest) char


YAWN!

But look at this:

depth : Bag x -> Nat
depth Air = 0
depth (Stuffed _ rest) = 1 + depth rest

sample : ?bag
sample = countOccurences "The quick, brown fox jumped over the lazy dog."

bag = proof search


When we do a depth sample, we get the not-surprising answer of 29 : Nat

Perhaps this could be made a tad bit more efficient?

Just perhaps.

Well, then, let's do that!


data Bag x = Air | Stuffed (x, Nat) (Bag x) (Bag x)

We make Bag balanced, with the add-function, doing the work of (very simply) branching off new nodes:

add : Ord x => Bag x -> x -> Bag x
add Air x = Stuffed (x, 1) Air Air
add (Stuffed (z, y) less more) x =
    case (compare x z) of
        LT => Stuffed (z, y) (add less x) more
        GT => Stuffed (z, y) less (add more x)
        EQ => Stuffed (z, y + 1) less more


Then all the other functions change ('morph') to work with a tree, not a list and work with Ord elements, not with (simply) Eq ones.

And so, the redefined depth-function gives a very different result:

depth sample ~> 9 : Nat

Not bad! Not bad! The improved data-structure improves efficiency across the board from O(N) to O(log N).

Hm, perhaps I'll have count return a dependently-typed pair, just as the library function filter does on List types, but not tonight.

Good night, Moon!
Categories: Offsite Blogs

Some thoughts on Isomorphic Types

Haskell on Reddit - Sun, 07/20/2014 - 4:21pm

Some Haskell types are isomorphic, which means we have functions (A and B are the isomorphic types)

a_to_b :: A -> B b_to_a :: B -> A

which satisfy the laws

a_to_b . b_to_a = id :: A -> A b_to_a . a_to_b = id :: B -> B

A simple example would be the types (a,(b,c)) and ((a,b),c) with the functions being

assoc (a,p) = ((a, fst p), snd p) assoc' (p, c) = (fst p, (snd p, c)

What this means is that the types are essentially the same with the only difference being their representation. This made me wonder whether it would be a good thing to have the ability to use isomorphic types interchangably on the typelevel. By this I mean that one can declare types as isomorphic by providing the correct functions, the default type to use when one of them is encountered and the typechecker actually treats them as the same type (essentially by inserting the transformation function where needed).

The reason why I thought about this is the following:

Consider a function (<||>) :: (a -> b) -> (c -> d) -> ((a,c) -> (b,d)) which turns two functions into a function on pairs. Since (a,(b,c)) and ((a,b),c) are isomorphic (<||>) behaves like an associative function but one is not able to use it like that, since the types get in the way.

Not only that but since the types ((),a), (a,()) and a are also all isomorphic id| :: () -> () would satisfy the laws of the neutral element of (<||>) but again you can't really use it that way since the types get messed up.

Quick insert: Since I am describing something similar to a monoid and also similar to the category class, I just did a quick google search and it looks like I am describing what makes up a monoidal category. So I guess one thing which would speak for having something like this would be that you have less cumbersome category theoretic things.

So assume Haskell allows you to make declarations like this:

isomorphic a (a,()) to a = (a,()) from (a,()) = a default a -- laws: to . from $ p == id p -- from . to $ a == id a

This means, that whenever the type (a,()) is encountered there is an implicit insertion of from changing the type to a allowing them to be used interchangably.

Would this be more of a good thing or more of a bad thing?

submitted by Pseudoradius
[link] [24 comments]
Categories: Incoming News

Obtaining kind of a HsType

haskell-cafe - Sun, 07/20/2014 - 1:45pm
Dear Haskell-café, I'm trying to get some information of the kinds of types in a program. In particular, I want to obtain the kinds of arguments to type family instances, that is, given: type family F a b :: Nat type instance F (List k) b = b I would like to obtain the kinds of "k" and "b" in the left-hand side of the type instance. In particular, I'm obtaining type family instance information via LTyFamInstEqn [ http://www.haskell.org/ghc/docs/latest/html/libraries/ghc/HsDecls.html#t:LTyFamInstEqn]. Inside, I get a list of binders of type HsWithBndrs [LHsType name]. I'm assuming each of the LHsTypes inside is a pattern in the type family instance. Thus, I'm looking at those elements and try to find their kind there. Thus, the specific question is: given a HsType, can I obtain its kind somehow? Thanks in advance _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Mutable State in Haskell

Haskell on Reddit - Sun, 07/20/2014 - 12:20pm
Categories: Incoming News

JP Moresmau: BuildWrapper/EclipseFP and GHC 7.8

Planet Haskell - Sun, 07/20/2014 - 11:24am
I've been working on some issues related to GHC 7.8 in BuildWrapper and EclipseFP. On the EclipseFP side, mainly the quickfixes are affected, because EclipseFP parses the GHC error messages to offer them, and the quotes characters have changed in the GHC 7.8 messages.

On the BuildWrapper side, things are more complex. Adapting to API changes wasn't a big deal, but it seems that GHC bugs involving the GHC API, static linking and other unknowns cause some things to break. The solution I've found was to build BuildWrapper with the -dynamic flag. But I couldn't upload this to hackage because Cabal thinks that -dynamic is a debug flag (it starts with d). I've sent a bug fix to Cabal, so in the next release that'll be fixed. So if you're using GHC 7.8 and BuildWrapper, you may want to rebuild the executable with -dynamic (uncomment the relevant line in the cabal file).

Note: BuildWrapper comes with a comprehensive test suite (90 tests covering all aspects). So you can always build the tests and run them to ensure everyting is OK on your system.

Happy Haskell Hacking!

Categories: Offsite Blogs

Network.CGI maintenance - character encodings

libraries list - Sun, 07/20/2014 - 9:43am
There is a problem with character handling for form inputs in Network.CGI. Back in December 2013 I emailed the listed maintainer — Anders Kaseorg <andersk< at >mit.edu> — and got no response. I mentioned the issue on here shortly after that. I’ve now tracked the problem down to web browsers using Windows-1252 as the de-facto standard for form data, patched the code to take account of this and sent another message a to andersk fortnight ago, again with no response. Is there someone out there with commit rights to whom I can send the patch?
Categories: Offsite Discussion

This just in, from my local GHC/Cabal checkout... (re: Cabal Hell)

Haskell on Reddit - Sun, 07/20/2014 - 9:00am

Transcript: http://lpaste.net/107785

Commentary: Here's what the test is doing:

  1. It builds and installs a package p-1.0, which contains "module P where p = 1"
  2. It builds and installs a package q, depending on p, which contains "module Q where import P; q = p + 10"
  3. It builds and installs a package p-1.1, which contains "module P where p = 1"
  4. It non-destructively reinstalls package q, but this time building against p-1.1 instead of p-1.0
  5. It builds an executable r (building against p-1.1 and q-1.0)
  6. With the same package database, we specify constraint that p==1.0, and rebuild executable r, which prints the value of q (building against p-1.0 and the other instance of q-1.0)
  7. It tests the two executables to make sure they behave as expected

There are still a minor pile of kinks to work out (in particular, only cabal configure understands this; cabal install's dependency solver also has to be clued in), but from here, it should be possible to do away with one of the major use-cases for Cabal sandboxes and put them all in the same package database, and support a 'cabal upgrade' command.

P.S. It's also possible to link q-1.0(p-1.0) and q-1.0(p-1.1) together in the same program, although I don't think this feature will be too useful without Backpack-like holes.

submitted by ezyang
[link] [13 comments]
Categories: Incoming News

Failure compiling ghc-mtl with ghc-7.8.{2,3}

glasgow-user - Sun, 07/20/2014 - 8:26am
I was trying to upgrade to ghc-7.8 the other day, and got this compilation failure when building ghc-mtl-1.2.1.0 (see the end of the message). I'm using the haskell overlay on Gentoo Linux straight out of the box, no local cabal installations of anything. Now I was told that other people can compile ghc-mtl with 7.8 just fine, so there must be something broken in my specific configuration. What would be an effective way to approach the situation? In the sources I see that an instance of MonadIO GHC.Ghc does exist. I don't understand these errors. Are there multiple different MonadIO classes in different modules? Thank you and happy hacking. Now the errors: Control/Monad/Ghc.hs:42:15: No instance for (GHC.MonadIO Ghc) arising from the 'deriving' clause of a data type declaration Possible fix: use a standalone 'deriving instance' declaration, so you can specify the instance context yourself When deriving the instance for (GHC.ExceptionMonad Ghc) Control/Monad/Ghc.hs:46:15
Categories: Offsite Discussion

Creating a Point

haskell-cafe - Sat, 07/19/2014 - 11:44pm
Hello, I was talking to friends about how could you make a Point type in haskell. It's intuitive to make a 2D point such as: type Point2D = (Double, Double) Let's define one operation on this new type: add2D (x1, y1) (x2, y2) = (x1+x2, y1+y2) Let's say now we want a 3D point. Then we'd be tempted to do: type Point3D = (Double, Double, Double) add3D (x1, y1, z1) (x2, y2, z2) = (x1+x2, y1+y2, z1+z2) Although those types work great and you could make a type class so you don't have to suffix each function with 2D and 3D. It feels like we are just repeating code when defining the add function. If we want to go 4D, 5D, etc it would be more repeated code. Using a list would be more general: type Point = [Double] now we have a nice, general add function add = zipWith (+) It's not so fun that we are able to do something like: add [2,3] [5,7,11] We have no type-safety that we can only operate on points with the same dimension. How could we address this? Can we make a general
Categories: Offsite Discussion

How many Haskell programmers are there?

haskell-cafe - Sat, 07/19/2014 - 11:17pm
Obviously this is a very fuzzy question. But what's the credible range of answers? Here's one: http://steve-yegge.blogspot.ca/2010/12/haskell-researchers-announce-discovery.html 38
Categories: Offsite Discussion

ANN: hackage-diff - Compare the public API ofdifferent versions of a Hackage library

haskell-cafe - Sat, 07/19/2014 - 8:43pm
Just a first shot at the problem, hope it’s useful to somebody! https://github.com/blitzcode/hackage-diff Cheers, Tim
Categories: Offsite Discussion

Mark Jason Dominus: Similarity analysis of quilt blocks

Planet Haskell - Sat, 07/19/2014 - 6:00pm

As I've discussed elsewhere, I once wrote a program to enumerate all the possible quilt blocks of a certain type. The quilt blocks in question are, in quilt jargon, sixteen-patch half-square triangles. A half-square triangle, also called a “patch”, is two triangles of fabric sewn together, like this:

Then you sew four of these patches into a four-patch, say like this:

Then to make a sixteen-patch block of the type I was considering, you take four identical four-patch blocks, and sew them together with rotational symmetry, like this:

It turns out that there are exactly 72 different ways to do this. (Blocks equivalent under a reflection are considered the same, as are blocks obtained by exchanging the roles of black and white, which are merely stand-ins for arbitrary colors to be chosen later.) Here is the complete set of 72:

It's immediately clear that some of these resemble one another, sometimes so strongly that it can be hard to tell how they differ, while others are very distinctive and unique-seeming. I wanted to make the computer classify the blocks on the basis of similarity.

My idea was to try to find a way to get the computer to notice which blocks have distinctive components of one color. For example, many blocks have a distinctive diamond shape in the center.

Some have a pinwheel like this:

which also has the diamond in the middle, while others have a different kind of pinwheel with no diamond:

I wanted to enumerate such components and ask the computer to list which blocks contained which shapes; then group them by similarity, the idea being that that blocks with the same distinctive components are similar.

The program suite uses a compact notation of blocks and of shapes that makes it easy to figure out which blocks contain which distinctive components.

Since each block is made of four identical four-patches, it's enough just to examine the four-patches. Each of the half-square triangle patches can be oriented in two ways:

  

Here are two of the 12 ways to orient the patches in a four-patch:

  

Each 16-patch is made of four four-patches, and you must imagine that the four-patches shown above are in the upper-left position in the 16-patch. Then symmetry of the 16-patch block means that triangles with the same label are in positions that are symmetric with respect to the entire block. For example, the two triangles labeled b are on opposite sides of the block's northwest-southeast diagonal. But there is no symmetry of the full 16-patch block that carries triangle d to triangle g, because d is on the edge of the block, while g is in the interior.

Triangles must be colored opposite colors if they are part of the same patch, but other than that there are no constraints on the coloring.

A block might, of course, have patches in both orientations:

All the blocks with diagonals oriented this way are assigned descriptors made from the letters bbdefgii.

Once you have chosen one of the 12 ways to orient the diagonals in the four-patch, you still have to color the patches. A descriptor like bbeeffii describes the orientation of the diagonal lines in the squares, but it does not describe the way the four patches are colored; there are between 4 and 8 ways to color each sort of four-patch. For example, the bbeeffii four-patch shown earlier can be colored in six different ways:

              

In each case, all four diagonals run from northwest to southeast. (All other ways of coloring this four-patch are equivalent to one of these under one or more of rotation, reflection, and exchange of black and white.)

We can describe a patch by listing the descriptors of the eight triangles, grouped by which triangles form connected regions. For example, the first block above is:

   b/bf/ee/fi/i

because there's an isolated white b triangle, then a black parallelogram made of a b and an f patch, then a white triangle made from the two white e triangles, then another parallelogram made from the black f and i, and finally in the middle, the white i. (The two white e triangles appear to be separated, but when four of these four-patches are joined into a 16-patch block, the two white e patches will be adjacent and will form a single large triangle: )

The other five bbeeffii four-patches are, in the same order they are shown above:

b/b/e/e/f/f/i/i b/b/e/e/fi/fi b/bfi/ee/f/i bfi/bfi/e/e bf/bf/e/e/i/i

All six have bbeeffii, but grouped differently depending on the colorings. The second one ( b/b/e/e/f/f/i/i) has no regions with more than one triangle; the fifth ( bfi/bfi/e/e) has two large regions of three triangles each, and two isolated triangles. In the latter four-patch, the bfi in the descriptor has three letters because the patch has a corresponding distinctive component made of three triangles.

I made up a list of the descriptors for all 72 blocks; I think I did this by hand. (The work directory contains a blocks file that maps blocks to their descriptors, but the Makefile does not say how to build it, suggesting that it was not automatically built.) From this list one can automatically extract a list of descriptors of interesting shapes: an interesting shape is two or more letters that appear together in some descriptor. (Or it can be the single letter j, which is exceptional; see below.) For example, bffh represents a distinctive component. It can only occur in a patch that has a b, two fs, and an h, like this one:

and it will only be significant if the b, the two fs, and the h are the same color:

in which case you get this distinctive and interesting-looking hook component.

There is only one block that includes this distinctive hook component; it has descriptor b/bffh/ee/j, and looks like this: . But some of the distinctive components are more common. The ee component represents the large white half-diamonds on the four sides. A block with "ee" in its descriptor always looks like this:

and the blocks formed from such patches always have a distinctive half-diamond component on each edge, like this:

(The stippled areas vary from block to block, but the blocks with ee in their descriptors always have the half-diamonds as shown.)

The blocks listed at http://hop.perl.plover.com/quilt/analysis/images/ee.html all have the ee component. There are many differences between them, but they all have the half-diamonds in common.

Other distinctive components have similar short descriptors. The two pinwheels I mentioned above are gh and fi, respectively; if you look at the list of gh blocks and the list of fi blocks you'll see all the blocks with each kind of pinwheel.

Descriptor j is an exception. It makes an interesting shape all by itself, because any block whose patches have j in their descriptor will have a distinctive-looking diamond component in the center. The four-patch looks like this:

so the full sixteen-patch looks like this:

where the stippled parts can vary. A look at the list of blocks with component j will confirm that they all have this basic similarity.

I had made a list of the descriptors for each of the the 72 blocks, and from this I extracted a list of the descriptors for interesting component shapes. Then it was only a matter of finding the component descriptors in the block descriptors to know which blocks contained which components; if the two blocks share two different distinctive components, they probably look somewhat similar.

Then I sorted the blocks into groups, where two blocks were in the same group if they shared two distinctive components. The resulting grouping lists, for each block, which other blocks have at least two shapes in common with it. Such blocks do indeed tend to look quite similar.

This strategy was actually the second thing I tried; the first thing didn't work out well. (I forget just what it was, but I think it involved finding polygons in each block that had white inside and black outside, or vice versa.) I was satisfied enough with this second attempt that I considered the project a success and stopped work on it.

The complete final results were:

  1. This tabulation of blocks that are somewhat similar
  2. This tabulation of blocks that are distinctly similar (This is the final product; I consider this a sufficiently definitive listing of “similar blocks”.)
  3. This tabulation of blocks that are extremely similar

And these tabulations of all the blocks with various distinctive components: bd bf bfh bfi cd cdd cdf cf cfi ee eg egh egi fgh fh fi gg ggh ggi gh gi j

It may also be interesting to browse the work directory.

Categories: Offsite Blogs

ghc 7.8 and ghc-mtl

Haskell on Reddit - Sat, 07/19/2014 - 4:13pm

I'm trying to build ghc-mtl-1.2.1.0 with ghc-7.8.3, getting these errors. Any ideas on how to fix those? What exactly causes them?

submitted by ihamsa
[link] [2 comments]
Categories: Incoming News

Export a type and its record-syntax functions, but not the constructor

Haskell on Reddit - Sat, 07/19/2014 - 3:31pm

I have the follow data type:

data X = X { getName :: String, getAddress :: Address }

When exporting this, I would like to export the type X and the functions getName and getAddress without exporting the type constructor X.

Is there a simple syntax to do this without having to name every single function and type in the module export statement?

I tried googling this but I only am finding examples of exporting only the type or exporting certain functions in the construction. ie:

module ... ( X(getName, getAddress) ) where

...will do what I want, but that means I have to explicitly name every function and type. Any syntactic sugar out that would do this?

submitted by Die-Nacht
[link] [6 comments]
Categories: Incoming News

hackage-diff: Compare the public API of different versions of a Hackage library

Haskell on Reddit - Sat, 07/19/2014 - 1:34pm

A couple of days ago, in the GHC 7.8.3 release thread, Michael Snoyman and Austin Seipp had the following exchange:

Now, what would be nice if we had some kind of report of all API changes between releases, but that's really a general purpose tool that would make life nicer for many different package users, not just ghc the library.

Can somebody just create a kickstarter for this or something already? I've been wishing for this tool for forever.

I found myself agreeing with that a lot. I constantly wonder what exactly has changed between two releases of a library. I thought, maybe I can write a tool like that, how hard can it be?

Slightly harder than I thought, as usual. But yeah, here it is, my first shot at the problem:

https://github.com/blitzcode/hackage-diff

It actually works pretty well in practice! Please let me know if this is useful for you, or if you can think of a way to make it nicer.

submitted by SirRockALot1
[link] [31 comments]
Categories: Incoming News