On Wed, 2002-08-21 at 16:52, Hal Daume III wrote:

I would consider using a prefix trie. Unfortunately, such a structure is not built in to Haskell.

Thanks for this! It seems that this kind of data structure is what I am looking for. [begin aside] It seems a pity that one needs to give the data type a special name in order for it to be recursive. What I mean, is that other types can be expressed using built in manipulators, eg [(Int,[Char])] Of course you can use "data" to create specialized types which are essentially the same in structure, but earmarked for specialized use, but there is always the "raw" type to use as a default... But the same is not true (so it seems) for recursive types. Ie, it would be nice to represent what you call "PreTrie" as a raw type. Imagine you used the '*' symbol to mean "recursively refer to yourself", then you could write [(a, (Bool, *))] to be the "raw" version of PreTrie. This would mean you also did not need to worry about using "helper" functions like insert' and elem'. Anyway, that's just a few thoughts I've had --- perhaps they are naive? After all, I am fairly new to Haskell :-) [end aside]

A naive implementation would be something like (I haven't tested/compiled this code, so there are 'bugs'...consider it 'psuedo-haskell'):

I've taken your code and fixed the 'bugs' (I think). I've got a few questions. Here's the fixed version, along with my questions: data PreTrie a = PreTrie [(a, (Bool, PreTrie a))] -- (element, is-element-in-trie, children) Why did you call it "PreTrie" and not just "Trie"? Any particular reason? empty :: PreTrie a empty = PreTrie [] insert :: Eq a => PreTrie a -> [a] -> PreTrie a insert (PreTrie l) a = PreTrie (insert' l a) insert' [] [x] = [(x, (True, empty))] insert' [] (x:xs) = [(x, (False, insert empty xs))] insert' ((a,(b,c)):ls) [x] | a == x = (a,(True,c)) : ls | otherwise = (a,(b,c)) : insert' ls [x] insert' ((a,(b,c)):ls) (x:xs) | a == x = (a,(b,insert c xs)) : ls | otherwise = (a,(b,c)) : insert' ls (x:xs) varElem :: Eq a => PreTrie a -> [a] -> Bool varElem (PreTrie l) a = varElem' l a Using just "elem" as you had before, caused hugs to give me this error: Reading file "PreTrie.hs": ERROR PreTrie.hs:23 - Definition of variable "elem" clashes with import any idea why? varElem' [] _ = False varElem' ((a,(b,c)):ls) [x] | a == x = b | otherwise = varElem' ls [x] varElem' ((a,(b,c)):ls) (x:xs) | a == x = varElem c xs | otherwise = varElem' ls (x:xs) When I wanted to test this stuff in hugs, I had to do things like: Main> varElem (insert (insert (insert empty "a") "b") "ab") "b" True The way I would do things in an imperative language would be something like: x = insert empty "a" x = insert x "b" x = insert x "ab" ... varElem x "b" Now obviously I can't do this, but is there some different technique for building up a data structure like this, or is it just a case of me getting used to long lines and lots of brackets? One more thing... when I did: Main> insert (insert (insert empty "a") "b") "ab" ERROR - Cannot find "show" function for: *** Expression : insert (insert (insert empty "a") "b") "ab" *** Of type : PreTrie Char I tried to define show :: (PreTrie a) -> String show (PreTrie l) = show l but got ERROR PreTrie.hs:35 - Definition of variable "show" clashes with import Am I on the right track? Thanks for your help! Cheers, Mark.

On Wed, 21 Aug 2002, Hal Daume III wrote:

I snipped most of the aside :). The main problem with structures without names is that it would be very difficult for the typechecker to do its job (as I understand it, though certainly typechecking is not my forte). But basically, this amounts to the same thing as trying to say:

type MyList a = (a, MyList a)

First of all, there's no base case (like "[]" in lists or "Nothing" in Maybe, etc.). So we can sort of fix that by saying:

type MyList a = (a, Maybe (MyList a))

So the list ends when we get to 'Nothing'. The problem here is on the type inference. Suppose I write:

('a', Just ('b', Just ('c', Nothing)))

Now, for a human point of view, this doesn't pose a problem. This is of type MyList Char. The problem is that haskell uses types eagerly, so when it gets down to 'Nothing', it will say, "okay, what type does this have? ah, it must by 'MyList a'. What does MyList a mean? Oh, it means '(a, Maybe (MyList a))'. Let me substitute." It will then continue ad infinitum. Of course, it's not that stupid and will simply reject the type at the very begginning for having a loop.

Someone else will have to say a word or two about what would happen if type inference were done lazily, though presumably "bad things" would happen (and it's not even clear this would help).

It can be done, and it isn't even particularly difficult. The trick is just to make the type-checker use graph rather than term unification, which means that when two (possibly recursive) types are compared, the type-checker remembers which pairs of types it is currently comparing, and if it later encounters the same pair of types again (at a recursive occurrence), simply assumes they match --- any failure would be caught by the previous (enclosing) comparison. It's the standard way a graph traversal avoids falling into a loop on cyclic graphs. But indeed, "bad things" happen. The bad things are that type errors would be reported later in some cases. The effect of allowing recursive types is that, every time hugs reports "unification would give infinite type" (or corresponding messages from other compilers), the definition concerned *would actually be type correct*. In a few cases (such as the one that kicked this discussion off), that is actually what we want. The trouble is that, in many other cases, the program is actually wrong! For example, look at f x y = if x==0 then y else f (x-1) Clearly a type error, right? (I left out the second parameter in the recursive call). But the error message from hugs is ERROR Junk.hs:1 - Type error in function binding *** Term : f *** Type : a -> b -> b *** Does not match : a -> b *** Because : unification would give infinite type which means that if recursive types were allowed, then this definition would be type correct! Its type would be f :: Num a => a -> b where b = b -> b (We can see that if b = b -> b, then the two types in the error message above actually do match). The trouble is that you can't actually call this function in any useful way. If you try, say with the call f 10 15 then you'll get an error message. In this case, Hugs would probably say ERROR - Illegal Haskell 98 class constraint in inferred type *** Expression : f 10 15 *** Type : Num b => b where b = b -> b Now, when you forget a parameter, one can perhaps question just how friendly a way today's error message is of telling you so. But making type definitions containing such errors type correct until they are used is scary! And that's the reason recursive types have never been added to Haskell. The consequences for type error reporting just seem to be too horrible to contemplate. I should add that recursive types ARE implemented in OCAML --- but after experiencing just these kinds of problems, recursion was restricted to OCAML object types, where it clearly doesn't cause much problem. John Hughes

On 23 Aug 2002, Dr Mark H Phillips wrote:

Am I right in thinking the trade-off is between * the expressability power of the type system; and * the ability pick up certain forms of human error?

Well, yes. When you extend the power of the type system like this, you are allowing more programs to typecheck. In this case, we suspect that "the majority" (whatever that means) of the newly accepted programs are actually erroneous. That doesn't make a strong case for the extension -- even if it would sometimes be useful.

Why not allow infinite types thereby gaining extra power which may sometimes be useful, but introduce the option (in hugs or ghc) of providing a warning every time "unification would give infinite type"? This would allow us to "have our cake and eat it too"! (But probably there's a catch:-)

I can imagine a "-fallow-infinite-types" flag to ghc --- goodness knows, the type-checker has enough other flags of that sort! You can always try to persuade Simon to put it in. But I don't fancy your chances: the case for it just isn't very strong. John

On Wed, 2002-08-21 at 17:50, Dylan Thurston wrote:

This is the same as one way of representing search trees, called a "trie". Two representations in Haskell are:

...

data Trie a = Trie [(a, Trie a)]

I touched on the following in my response to Hal Daume's email, but it's probably worth asking properly... Am I right in thinking there is no way of doing this using an "essential" type? What I mean is, data Age = Age Int data Names = Names [String] data Person = Person (Age,Names) can be used to represent the details of a person, but the "essential type" corresponding to Person, is (Int,[String]) Having the type Person is useful in that, basically it is a duplicate of the essential type, to be used for a specialized purpose. But there is always the option of converting it to the essential type, thereby allowing higher order functions to be applied to it. But for the "Trie" type you have above, I am not aware of any way of converting this to an "essential type". What I am thinking, is something like [(a, *)] where '*' means to recursively refer to yourself.

or, using the FiniteMap module, if you only care about the set of lists,

...

data Trie a = Trie (FiniteMap a (Trie a))

Am I right in thinking that FiniteMap is like a list, but that it is more efficient with "random access" use than a normal list? Thanks for your help, Mark.

On 2002-08-22T17:04:02+0930, Dr Mark H Phillips wrote:

But for the "Trie" type you have above, I am not aware of any way of converting this to an "essential type". What I am thinking, is something like [(a, *)] where '*' means to recursively refer to yourself.

I guess this depends on what you mean by "essential type". If you are willing to grant me a few additional types as essential ones: data Fix f = Fix (f (Fix f)) newtype Pair f g a = Pair (f a, g a) newtype Compose f a = Compose (f a) newtype Self a = Self a newtype Const t a = Const t then I can build a type roughly isomorphic to what you call "[(a,*)]": type T a = Fix (Compose [] (Pair (Const a) Self)) For example, the value "[('a', [])]" would be written Fix (Compose [Pair (Const 'a', Self (Fix (Compose [])))]) :: Fix (Compose [] (Pair (Const Char) Self)) One place to learn more about these things is section 4 of Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In Johan Jeuring and Erik Meijer, editors, Advanced Functional Programming: First International Spring School on Advanced Functional Programming Techniques, number 925 in Lecture Notes in Computer Science, pages 97-136. Springer-Verlag, Berlin, 1995. http://www.cse.ogi.edu/~mpj/pubs/springschool.html The paper is also a great read otherwise! -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig http://oxford.freeexchange.co.uk/pages/6001.html