Binding together data, types and functions

Question

I want to model a large tree (or forest) of some regular structure - tree can be decomposed to small tree (the irregular part) and (i.e.) large list of params, each of them with each of nodes make a node of big tree.

So, I want a data structure, where each node in a tree is representing many nodes. And real node is of type (node,param).

For algorithms that work on this kind of trees type of that param does not mattter. They are just placeholders. But some data should be possible to extract from the plain param or combination of node and param, and all possible params should be iterable. All that kinds of data is known apriori, they reflect semantic of that tree.

So, actual type, semantics and stuff of param is up to implementation of tree.

I model it in C++ using nested typedefs for params type, fixed method names for all kind of stuff that should be available to algorithm (this two together making a concept) and templates for algorithm itself.

I.e. if I want to associate with each node of big tree an integer, I would provide a function int data(const node& n, const param& p), where param is available as nested typedef, and algorithm could get list of all available params, and call data with nodes of interest and each of params

I have some plain data type, i.e. tree data, like this

data Tree = Node [Tree] | Leaf

Now I want to package up:

concrete tree
some type
some values of that type
some functions operating on (that concrete) tree nodes and (that) values

So one can write some function that use this packaged up types and functions, like, generic way.

How to achieve that?

With type families I came to

class PackagedUp t where
  type Value t

  tree :: Tree t
  values :: [Value t]
  f :: Tree t -> Value t -> Int

Tree now become Tree t because type families want type of their members to depend on typeclass argument.

Also, as in https://stackoverflow.com/a/16927632/1227578 type families to deal with injectivity will be needed.

With this I can

instance PackagedUp MyTree where
  type Value MyTree = (Int,Int)
  tree = Leaf
  values = [(0,0),(1,1)]
  f t v = fst v

And how to write such a function now? I.e. a function that will take root of a tree, all of values and make a [Int] of all f tree value.

Your definition of Tree is not what you want, and I'm pretty sure you don't need to go as far as type families to solve your problem. To give an useful answer, however, we need to know what you want f to do, as that is not very clear from the code. — duplode
Actually I want to model certain kind of a game tree, I'll explain in question. I already did that in C++, and now trying to port that to Haskell. Don't ask why) — Mikhail Cheshkov
I think you are complicating things. Just make a module with the things you want to bundle. — augustss
@augustss I'm trying to make a generic data structure and algorithm for that. Maybe it's too complicated solution, or even maybe I should not bother memory for huge trees in haskell, but certainly I want a way to handle generic things. — Mikhail Cheshkov
Before you attempt to generalize using a class, try a more specific implementation. And try generalizing with type parameters and functions rather than a class. — augustss

duplode duplode · Accepted Answer · 2014-04-26T22:01:04

First of all, your tree type should be defined like this:

data Tree a = Node a [Tree a] | Leaf

The type above is polymorphic. As far as semantics go that resembles what we would call a generic type in OO parlance (in C# or Java we might write Tree<A> instead). A node of a Tree a holds a value of type a and a list of subtrees.

Next, we come to PackagedUp. Classes in Haskell have little to do with the OO concept of the same name; they are not meant to package data and behaviour together. Things are actually much simpler: all you need to do is defining the appropriate functions for your tree type

getRoot :: Tree a -> Maybe a
getRoot Leaf       = Nothing
getRoot (Node x _) = Just x

(Returning Maybe a is a simple way to handle failure with type safety. Think of the Nothing value as a polite cousin of null that doesn't explode with null reference exceptions.)

One thing that type classes are good at is in expressing data structure algorithm interfaces such as the ones you allude to. One of the most common classes is Functor, which provides a general interface for mapping over data structures.

instance Functor Tree where
    fmap f Leaf        = Leaf
    fmap f (Node x ts) = Node (f x) (fmap f ts)

fmap has the following polymorphic type:

fmap :: Functor f => (a -> b) -> f a -> f b

With your tree, it specialises to

fmap :: (a -> b) -> Tree a -> Tree b

and with lists (as in fmap f ts) it becomes

fmap :: (a -> b) -> [a] -> [b]

Finally, the Data.Tree module provides a data structure which looks a lot like what you want to define.

Binding together data, types and functions

1 Answers