Alp Mestanogullari's Blog

A French community for Haskell

Posted in Uncategorized by alpmestan on 2011/10/09

During the past few months, there has been some growing activity in the (hidden) French circles of the Haskell community. A few people, including myself, are trying to increase the interest around Haskell in the French-speaking communities. You may (or may not) have noticed the translation of Learn You A Haskell that is available here, in French. We also have an IRC channel, #haskell-fr (access it through Freenode’s webchat), and a mailing list. Please let us know about you if you are a French-speaking haskeller!

But we would like to get it a step further. We are currently considering the idea of a French hackathon. We already have been offered a room for 3 days in June 2012, in conjunction with a French Perl event. So one of the reasons behind this blog post is to get some feedback about this, in addition to letting people know about the French community. Who would be interested in attending such an event? This would be in Strasbourg, France for the moment. Note that this would not necessarily be restricted to French haskellers! The format would be a pretty much classical Hackathon: potential talks and a lot of Haskell hacking. So please let us know if you’d be interested in attending this (by commenting this post, the IRC channel or the mailing list).

On a side note, these past few days, I updated one of my libraries: statistics-linreg and published one too: kmeans-vector. It performs the k-means clustering algorithm on a list of points, and can lead to “pretty” graphics like the following.

Performing k-means on 10,000 points with 4 clusters

Tagged with: , ,

Templates for unique id generation for types : a beginning

Posted in Uncategorized by alpmestan on 2009/10/31

After reading one of the comments on this blog post, I decided to publish here a proof of concept for the generation of unique ids for types.

Basically, it’s just about one template structure, using very basical templates techniques : specialization, metaprogramming-level recursion and nested enum for the computation. Either a familiarity with template metaprogramming or with functional programming is enough to understand the following code.

If you’re familiar with any scheme of functional recursion, or recursion in its mathematical sense, you’ll get it quite easily. Mathematically, we’re somehow defining a recursive function generate_id this way :

generateid(int) = 5
generateid(char) = 7
\forall T,\, generateid(\textit{pointer to T}) = 2 \cdot generateid(T)
\forall T,\, generateid(\textit{ref to T}) = 3 \cdot generateid(T)
\forall T,\, generateid(\textit{vector of T}) = 11 \cdot generateid(T)

Which, in C++, becomes :

template <typename T>
struct id_generator;

template <typename T>
struct id_generator<T*>
{
    enum { result = id_generator<T>::result*2 };
};

template <typename T>
struct id_generator<T&>
{
    enum { result = id_generator<T>::result*3 };
};

template <typename T>
struct id_generator< std::vector<T> >
{
    enum { result = id_generator<T>::result*11 };
};

template <>
struct id_generator<int>
{
    enum { result = 5 };
};

template <>
struct id_generator<char>
{
    enum { result = 7 };
};

And a minimal example of use :

int main()
{
    std::cout << "int : " << id_generator< int >::result << std::endl
              << "char**** : " << id_generator< char**** >::result << std::endl
              << "vector<int> : " << id_generator< std::vector<int> >::result << std::endl;
    return 0;
}
/* Output :
int : 5
char**** : 112
vector<int> : 55
*/

To make it really usable, you’ll have to add much (much much much) more :

  • base types, like int and char here, which help for terminating the recursive call
  • composition rules, like vector, references and pointers here, which help for propagating the recursion

To ensure the uniqueness here, I use prime numbers, simply [1]. Indeed, for the base types, I give a value being a prime number. For the different compositions, I multiply by a different prime number for each. However, most of you may have noticed that the id only lets you know about what type compositions and base types are used, but gives nothing about the order. If we add a rule for std::list, multiplying by 13 for example, then a list of vectors of ints will have the same id as a vector of lists of int. It’d need additional code and workarounds to take the order of the compositions in account — I guess it is possible though. If any reader here comes up with a solution, let us know. A possible solution would be to drop prime numbers, since they rely on a commutative (abelian) ring [2].

[1] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
[2] http://en.wikipedia.org/wiki/Commutative_ring

Tagged with: , ,
Follow

Get every new post delivered to your Inbox.

Join 251 other followers