News aggregator

Dynamic loadable modules?

Haskell on Reddit - Sun, 03/15/2015 - 5:43pm

Is there an easy way to do dynamic loadable Haskell modules? For example I have the modules A, B, C and they all export something of type Something. Based on the arguments by which the application is invoked I'd like to do import a specified module.

The alternative is of course to create a datatype like:

data LoadModule = ModuleA Something | ModuleB Something | etc... type Modules = [LoadModule]

Where I would transform the given input in a datatype by which I could find the desired one via constructor pattern matching. However I'm going to have around 40+ such modules and there is a lot more boilerplate with this approach.

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

package ParsecToken

haskell-cafe - Sun, 03/15/2015 - 3:00pm
I am new to the community and learning Parsec, reading the tutorial "Parsec, a fast combinator Parse" by Daan Leijen. In the tutorial, the examples import the package called "ParsecToken" and I could not find this package any where (I found many variants like Text.Parsec.Token, Text.ParseCombinators.Parsec.Token etc.) So I was unable to execute those examples given there. Q1. How do I find the package name for "ParsecToken" so that I can do cabal import? Thanks. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Categories: Offsite Discussion

Question: Type System and N-Dimensional Vectors

Haskell on Reddit - Sun, 03/15/2015 - 2:02pm

AFAIK, in haskell, the two main ways to encode Vectors( In the mathematical sense ) are n-dimensional Tuples (t,t) or Lists [t]. Lists, of course, do not carry size information as part of their type. Tuples do, but the size must be constant--hardcoded into the type. My question is, is there any way to statically check vectors of arbitrary size. For instance, could we define a function like zip, which statically checks that its arguments are the same length, but doesn't specify the length. something like myZip:: vec t n -> vec t n -> vec (t,t) n. where t is the type of data held in the vector and n is the length. Thanks.

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

Brent Yorgey: Anafunctors

Planet Haskell - Sun, 03/15/2015 - 1:55pm

This is part four in a series of posts on avoiding the axiom of choice (part one, part two, part three).

In my previous post, we considered the “Axiom of Protoequivalence”—that is, the statement that every fully faithful, essentially surjective functor (i.e. every protoequivalence) is an equivalance—and I claimed that in a traditional setting this is equivalent to the axiom of choice. However, intuitively it feels like AP “ought to” be true, whereas AC must be rejected in constructive logic.

One way around this is by generalizing functors to anafunctors, which were introduced by Makkai (1996). The original paper is difficult going, since it is full of tons of detail, poorly typeset, and can only be downloaded as seven separate postscript files. There is also quite a lot of legitimate depth to the paper, which requires significant categorical sophistication (more than I possess) to fully understand. However, the basic ideas are not too hard to grok, and that’s what I will present here.

It’s important to note at the outset that anafunctors are much more than just a technical device enabling the Axiom of Protoequivalence. More generally, if everything in category theory is supposed to be done “up to isomorphism”, it is a bit suspect that functors have to be defined for objects on the nose. Anafunctors can be seen as a generalization of functors, where each object in the source category is sent not just to a single object, but to an entire isomorphism class of objects, without privileging any particular object in the class. In other words, anafunctors are functors whose “values are specified only up to unique isomorphism”.

Such functors represent a many-to-many relationship between objects of and objects of . Normal functors, as with any function, may of course map multiple objects of to the same object in . The novel aspect is the ability to have a single object of correspond to multiple objects of . The key idea is to add a class of “specifications” which mediate the relationship between objects in the source and target categories, in exactly the same way that a “junction table” must be added to support a many-to-many relationship in a database schema, as illustrated below:

On the left is a many-to-many relation between a set of shapes and a set of numbers. On the right, this relation has been mediated by a “junction table” containing a set of “specifications”—in this case, each specification is simply a pair of a shape and a number—together with two mappings (one-to-many relations) from the specifications to both of the original sets, such that a specification maps to a shape and number if and only if and were originally related.

In particular, an anafunctor is defined as follows.

  • There is a class of specifications.
  • There are two functions mapping specifications to objects of and .

, , and together define a many-to-many relationship between objects of and objects of . is called a specified value of at if there is some specification such that and , in which case we write . Moreover, is a value of at (not necessarily a specified one) if there is some for which .

The idea now is to impose additional conditions which ensure that “acts like” a regular functor .

  • Functors are defined on all objects; so we require each object of to have at least one specification which corresponds to it—that is, must be surjective.
  • Functors transport morphisms as well as objects. For each (the middle of the below diagram) and each in (the left-hand side below), there must be a morphism in (the right-hand side):

  • Functors preserve identities: for each we should have .
  • Finally, functors preserve composition: for all (in the middle below), , and (the left side below), it must be the case that :

Our initial intuition was that an anafunctor should map objects of to isomorphism classes of objects in . This may not be immediately apparent from the definition, but is in fact the case. In particular, the identity morphism maps to isomorphisms between specified values of ; that is, under the action of an anafunctor, an object together with its identity morphism “blow up” into an isomorphism class (aka a clique). To see this, let be two different specifications corresponding to , that is, . Then by preservation of composition and identities, we have , so and constitute an isomorphism between and .

There is an alternative, equivalent definition of anafunctors, which is somewhat less intuitive but usually more convenient to work with: an anafunctor is a category of specifications together with a span of functors where is fully faithful and (strictly) surjective on objects.

Note that in this definition, must be strictly (as opposed to essentially) surjective on objects, that is, for every there is some such that , rather than only requiring . Given this strict surjectivity on objects, it is equivalent to require to be full, as in the definition above, or to be (strictly) surjective on the class of all morphisms.

We are punning on notation a bit here: in the original definition of anafunctor, is a set and and are functions on objects, whereas in this more abstract definition is a category and and are functors. Of course, the two are closely related: given a span of functors , we may simply take the objects of as the class of specifications , and the actions of the functors and on objects as the functions from specifications to objects of and . Conversely, given a class of specifications and functions and , we may construct the category with and with morphisms in acting as morphisms in . From to , we construct the functor given by on objects and the identity on morphisms, and the other functor maps in to in .

Every functor can be trivially turned into an anafunctor . Anafunctors also compose. Given compatible anafunctors and , consider the action of their composite on objects: each object of may map to multiple objects of , via objects of . Each such mapping corresponds to a zig-zag path . In order to specify such a path it suffices to give the pair , which determines , , and . Note, however, that not every pair in corresponds to a valid path, but only those which agree on the middle object . Thus, we may take as the set of specifications for the composite , with and . On morphisms, . It is not hard to check that this satisfies the anafunctor laws.

If you know what a pullback is, note that the same thing can also be defined at a higher level in terms of spans. , the category of all (small) categories, is complete, and in particular has pullbacks, so we may construct a new anafunctor from to by taking a pullback of and and then composing appropriately.

One can go on to define ananatural transformations between anafunctors, and show that together these constitute a -category which is analogous to the usual -category of (small) categories, functors, and natural transformations; in particular, there is a fully faithful embedding of into , which moreover is an equivalence if AC holds.

To work in category theory based on set theory and classical logic, while avoiding AC, one is therefore justified in “mixing and matching” functors and anafunctors as convenient, but discussing them all as if they were regular functors (except when defining a particular anafunctor). Such usage can be formalized by turning everything into an anafunctor, and translating functor operations and properties into corresponding operations and properties of anafunctors.

However, as I will argue in some future posts, there is a better solution, which is to throw out set theory as a foundation of category theory and start over with homotopy type theory. In that case, thanks to a generalized notion of equality, regular functors act like anafunctors, and in particular AP holds.

References

Makkai, Michael. 1996. “Avoiding the Axiom of Choice in General Category Theory.” Journal of Pure and Applied Algebra 108 (2). Elsevier: 109–73.


Categories: Offsite Blogs

Jeremy Gibbons: Breadth-First Traversal

Planet Haskell - Sun, 03/15/2015 - 11:00am

Recently Eitan Chatav asked in the Programming Haskell group on Facebook

What is the correct way to write breadth first traversal of a ?

He’s thinking of “traversal” in the sense of the class, and gave a concrete declaration of rose trees:

It’s an excellent question.

Breadth-first enumeration

First, let’s think about breadth-first enumeration of the elements of a tree. This isn’t compositional (a fold); but the related “level-order enumeration”, which gives a list of lists of elements, one list per level, is compositional:

Here, is “long zip with”; it’s similar to , but returns a list as long as its longer argument:

(It’s a nice exercise to define a notion of folds for , and to write as a fold.)

Given , breadth-first enumeration is obtained by concatenation:

Incidentally, this allows trees to be foldable, breadth-first:

Relabelling

Level-order enumeration is invertible, in the sense that you can reconstruct the tree given its shape and its level-order enumeration.

One way to define this is to pass the level-order enumeration around the tree, snipping bits off it as you go. Here is a mutually recursive pair of functions to relabel a tree with a given list of lists, returning also the unused bits of the lists of lists.

Assuming that the given list of lists is “big enough”—ie each list has enough elements for that level of the tree—then the result is well-defined. Then is determined by the equivalence

Here, the of a tree is obtained by discarding its elements:

In particular, if the given list of lists is the level-order of the tree, and so is exactly the right size, then will have no remaining elements, consisting entirely of empty levels:

So we can take a tree apart into its shape and contents, and reconstruct the tree from such data.

Breadth-first traversal

This lets us traverse a tree in breadth-first order, by performing the traversal just on the contents. We separate the tree into shape and contents, perform a list-based traversal, and reconstruct the tree.

This trick of traversal by factoring into shape and contents is explored in my paper Understanding Idiomatic Traversals Backwards and Forwards from Haskell 2013.

Inverting breadth-first enumeration

We’ve seen that level-order enumeration is invertible in a certain sense, and that this means that we perform traversal by factoring into shape and contents then traversing the contents independently of the shape. But the contents we’ve chosen is the level-order enumeration, which is a list of lists. Normally, one thinks of the contents of a data structure as simply being a list, ie obtained by breadth-first enumeration rather than by level-order enumeration. Can we do relabelling from the breadth-first enumeration too? Yes, we can!

There’s a very clever cyclic program for breadth-first relabelling of a tree given only a list, not a list of lists; in particular, breadth-first relabelling a tree with its own breadth-first enumeration gives back the tree you first thought of. In fact, the relabelling function is precisely the same as before! The trick comes in constructing the necessary list of lists:

Note that variable is defined cyclically; informally, the output leftovers on one level also form the input elements to be used for relabelling all the lower levels. Given this definition, we have

for any . This program is essentially due to Geraint Jones, and is derived in an unpublished paper Linear-Time Breadth-First Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips that we wrote together in 1993.

We can use this instead in the definition of breadth-first traversal:

Categories: Offsite Blogs

Getting Into Netwire

Haskell on Reddit - Sun, 03/15/2015 - 5:32am
Categories: Incoming News

chat #haskell

Haskell on Reddit - Sun, 03/15/2015 - 5:05am
Categories: Incoming News

Wrong .hsc file paths on Windows

haskell-cafe - Sat, 03/14/2015 - 9:08pm
Hello, I was trying to port some of my code to Windows. I've installed GHC with MinGHC (https://github.com/fpco/minghc). Unfortunately some packages, namely zlib and network, won't install, with the same error: getModificationTime cannot locate a file like CodecCompressionZlibStream.hsc or NetworkSocketTypes.hsc. With zlib, I figured out I just need to change mentions of "Codec/Compression/(...)" adding two slashes instead of one. Now with network I'm stuck, I can't find where the path was set at all. Is there some step I should have done prior to installation that would get the paths right? Best regards, Marcin Mrotek
Categories: Offsite Discussion

Language extensions

Haskell on Reddit - Sat, 03/14/2015 - 3:26pm

One thing I am having a little trouble understanding is the number of language extensions in Haskell. Lens requires templates. Then there is OverloadedStrings. Is there any source that can explain the different extensions out there, what they do, and whether they are "OK" to use? Is there a reason that these extensions have not been merged into Haskell?

submitted by tempforfather
[link] [39 comments]
Categories: Incoming News

Why are ADTs necessary?

Haskell on Reddit - Sat, 03/14/2015 - 1:04pm

As I understand it, GHC Haskell compiles a lot of constructs out, ending up with a very simple language, Core. For example, typeclasses are compiled out, and the dictionaries are passed around explicitly.

I was wondering why Algebraic Data Types are not also compiled out. This would make Core simpler. An ADT like

data X = X1 Int | X2 Bool Int

could be represented as this type:

(Int -> r) -> (Bool -> Int -> r) -> r

and then pattern matching could be compiled to function application.

The two things that occur to me, as possible reasons why this is not done, are the resulting types being recursive, and possible difficulties with optimization.

The List type, for instance, would have to turn into a function with this type:

type List a = r -> (a -> List a -> r) -> r

This is a recursive type, and isn't allowed in Haskell; but recursive types aren't intractable or anything, they are supported in ocaml with the -rectypes flag.

The second issue is optimization: Just 5 can be stored and accessed as a very simple binary representation, something like {0x0001, 0x0005}. The equivalent without ADTs, (\f g -> g 5), would probably have a more complicated representation, unless special optimizations were applied to these kinds of expressions.

Is one of these issues the main reason that ADTs are kept even at the Core level? Or is it something else?

submitted by jpriestley
[link] [39 comments]
Categories: Incoming News

π-day

haskell-cafe - Sat, 03/14/2015 - 11:23am
Happy super pi day everybody! Henk-Jan van Tuyl
Categories: Offsite Discussion

Limit type variables to exclude function types?

Haskell on Reddit - Sat, 03/14/2015 - 10:07am

During some design thoughts for a small templating engine I recently had some ideas about automatically composing functions returning a Monoid with values of that Monoid into some sort of function taking all the parameters required by any of the functions (possibly eliminating duplicates if we ensure that every parameter type occurs only once).

So if we wanted to write an email to a person

data Person = Person { personFirstName :: Text , personLastName :: Text , personGender :: Gender } genderTitle :: Gender -> Text genderTitle Male = "Mister" genderTitle Female = "Ms"

about an event

data Event = Event { eventName :: Text , eventLocation :: Text }

instead of writing something ugly like

emailTemplate :: Person -> Event -> Text emailTemplate person event = concat [ "Hello " , genderTitle $ personGender person, " " , personFirstName person, " " , personLastName person, "\n\n" , "Want to come to ", eventName event, " at " , eventLocation event, "?" ]

we could write something more like

emailTemplate :: Person -> Event -> Text emailTemplate = "Hello " <++> genderTitle . personGender <++> " " <++> personFirstName <++> " " <++> personLastName <++> "\n\n" <++> "Want to come to " <++> eventName <++> " at " <++> eventLocation <++> "?"

where <++> is the operator I am having trouble implementing. I know that in this particular example NameFieldPuns or RecordWildCards would solve my problem mostly but the whole example is mostly to motivate the idea.

Basically the semantics of the <++> operator should be that it should work like Monoid's <> on values that are not a function type. On composing a function with a value it should return a function with the same parameters and compose the result of the input function when called with those parameters with the input value.

When composing two functions however it should essentially merge their parameter lists. This shouldn't be too hard by iterating over the parameter lists of the two functions but here I am running into problems because I haven't found a way to limit a type variable in Haskell to a non-function type.

Apparently I can limit a type variable to a function type like this

foo :: (a ~ (b -> c)) => a -> a foo = id bar = foo (1 :: Int) quux = foo (+1)

Here bar gives me a compile error as expected

FunctionVariableTest.hs:8:12: Couldn't match expected type ‘b -> c’ with actual type ‘Int’ Relevant bindings include bar :: b -> c (bound at FunctionVariableTest.hs:8:1) In the first argument of ‘foo’, namely ‘(1 :: Int)’ In the expression: foo (1 :: Int) In an equation for ‘bar’: bar = foo (1 :: Int)

However I haven't managed to do the opposite, limit it to a value that is not a function.

Is there a way to achieve this in current GHC/Haskell?

submitted by Taladar
[link] [16 comments]
Categories: Incoming News

Reddit Bot written in Haskell?

Haskell on Reddit - Sat, 03/14/2015 - 6:12am

I'd like to write a bot that does various things. Has anyone written or know of a good open source Haskell implementation of a simple Reddit bot? I'd like to avoid needing to swim through http requests and parsing out comments from xml and just focus on the "content" of what it does. I've glanced at a few implementations in Python but I like Haskell more.

submitted by TimTravel
[link] [12 comments]
Categories: Incoming News

How to not abuse tuples (or "the data.frame problem")

Haskell on Reddit - Sat, 03/14/2015 - 4:45am

Following a discussion on this thread, telling me that I was abusing tuples, I decided to post a separate question about giant tuples or an alternative to (R) data-frame. When I say giant tuples, I mean from 5-uples, to 50-uples+ ;-).

The general consensus seems to be that tuples should be avoided (especially long one) and (R) data.frame smells of bad design, therefore any related question are usually not considered as real world and as such does't come up with a "real world" asnwer . However I have a real case scenario where giant tuple/record is a necessity : generating corporate reports using Word (or equivalent).

An easy way to generate nice reports is to use Word and its mail merging feature. For people how doesn't know, you create a template document with fields and feed Word with a csv. Word instantiate the templates for each row, each field being a column in the csv.

So far so good, most of the reports are just map-reduce problems, seems an easy job for Haskell. The problem is , a simple report would have a minimum 20 fields, whereas a big one could have 50-80 fields, meaning as many column in a csv.

How do you deal with that in Haskell ? I know people will just answer : "create a big record with all you fields and the job is done" and that's probably the answer, however the workflow I'm use to (which is probably ) needs more flexibility.

I started writing those report in Excel. The workflow is basically, load a csv, and each time you need to compute something, create a new column (even intermediate results). Keeping intermediate result (as a column) is a good practice because it means than formula are shorter and if something gets wrong, you can easily find problem and/or rewrite formulat.

However, doing things manually becomes quickly a pain so I then used R. R with data.frame is great an allow to replicate this workflow. For people how doesn't R, data.frame basically a table (as in SQL or in a excel spreadsheet). They have rows, (named) columns and you can do everything you need with them (adding row, adding column, join them) etc ...

You can do things like that :

data1 <- read.csv(file1) -- read a csv data2 <- read.csv(file2) -- read another csv data <- merge(data1, data2) -- do a join using common columns data$q6 = roundTo(data$quantity, 6) -- round up quantities to multiple of 6. data$amount = data$q6*data$price -- great a new column : amount = price*q6

It's damm quick to write and you can't really beat it. However, 6 months later you have no idea how many columns data has, and worst, you don't know if quantity is coming originaly from file1 or file2.

I'm trying to do the same in Haskell. Reading a csv is easy. Merging them too (thanks to the these package. The main problem is data representation.

What's is hard to do in Haskell (but easy in R) is that each intermediate calcul (or steps) creates a new shape by extending the previous one.

For example

data1 would be (String, Int) (item code, quantity).
data2 would be (String, Double) (item code, price). the result of merge(data1,data2) , (String, Int, Double). when adding q6 : (String, Int, Double, Int). when adding amount : `(String, Int, Double, Int, Amount).

etc ...

This type extension ((String, Int, Double) => (String, Int, Double, Int) => (String, Int, Double, Int, Double) is needed for different reason and is the problem I would like to solve.

The different approach I found are, tuples, records, HList.Record and dataframe ?

tuples

Tuples are great mainly because you don't need to create a type but also because they come batteries including ie instantiate all the standard typeclass (like Monoid, csv reader etc ...). However, they don't compose well (how do you transform ((a,b), c) to (a, b,c), they are a pain to get/set value from , and worst, the common instances have a limit and each packages as it's own limit. For example, the morph package instantiate HFoldable for 13-uple whereas Monoid stops as 5-uples.

Record

I've been told that types are cheap in haskell, so I could indeed creates a new type for each steps. The main problems here are : instanciation of common typeclass (Monoid, fromCSv etc ..) and find a good name for each type variation (and their accessors).

Record with polymorphic tail

It's probably equivalent to HList.Record ...

HList.Record

HList.Record seems to tick all the boxes, they are extendable, easy to access etc ... However, I don't how well the perform with LOTS of fields. And, my main concern at the moment, is type signature. The type signature of a HList.Record with 10 fields would probabaly not fit in a page.

DataFrame

I've heard of a dataframe package but I don't know if it's ready and or is really different from the HList.Record approach.

Any thought are welcome :-)

submitted by maxigit
[link] [40 comments]
Categories: Incoming News