- Haskell-Cafe - Haskell.org

Re: [Haskell] Type-Level Naturals Like Prolog?
by Niklas Broberg 13 Jul '06

13 Jul '06

On 7/13/06, Jared Warren <jawarren(a)gmail.com> wrote: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. However, Idealised Prolog > does not have data structures, and does Peano numbers like: > > natural(zero). > natural(x), succ(x,y) :- natural(y) > > And I believe (but cannot confirm): > > succ(zero,y). > succ(x,y) :- succ(y,z) That is not a valid encoding of peano numbers in prolog, so I think that's where your problems stem from. :-) % defining natural numbers natural(zero). natural(s(X)) :- natural(X). % translate to integers toInt(zero, 0). toInt(s(X), N) :- toInt(X, Y), N is Y + 1. In the same style of reasoning for Haskell, we would define > data Zero > data Succ x > > class Natural x > instance Natural Zero > instance (Natural x) => Natural (Succ x) > > class Natural x => ToInt x where > toInt :: x -> Int > > instance ToInt Zero where > toInt _ = 0 > > instance (ToInt x) => ToInt (Succ x) where > toInt _ = toInt (undefined :: x) + 1 Or we could add the toInt method directly to the Natural class like you did above. So yes, we can mimic (some of) prolog in Haskell's type language. :-) /Niklas

1 0

Breaking cycles in a directed graph.
by Daniel McAllansmith 13 Jul '06

13 Jul '06

Hello. I'm currently using Data.Graph.Inductive to represent a directed graph. I want to detect all cycles within the graph and 'break' them by inserting a minimal number of nodes that are labelled with a special cycle-breaker label. Can anyone give me advice on a good algorithm for finding the cycles and finding the optimum edges to insert the cycle-breaking nodes on? Thanks Daniel

4 6

Re: [Haskell] Type-Level Naturals Like Prolog?
by dons＠cse.unsw.edu.au 13 Jul '06

13 Jul '06

jawarren: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. However, Idealised Prolog > does not have data structures, and does Peano numbers like: > > natural(zero). > natural(x), succ(x,y) :- natural(y) > > And I believe (but cannot confirm): > > succ(zero,y). > succ(x,y) :- succ(y,z) > > Why can't Haskell (with extensions) do type-level Peano naturals in > the same fashion? The code would be something like: > > >data Zero > > > >class Natural x where > > toInt :: x -> Integer > >instance Natural Zero where > > toInt _ = 0 > >instance (Natural x, Succ x y) => Natural y where > > toInt y = undefined + 1 > > > >class Succ x y > >instance Succ Zero y > >instance Succ x y => Succ y z > > > >zero = toInt (undefined :: Zero) -- THIS SUCCEEDS > > > >one = toInt (undefined :: (Succ Zero x) => x) -- THIS FAILS > Perhaps these will be useful? http://www.haskell.org/haskellwiki/Peano_numbers http://www.haskell.org/haskellwiki/Type_arithmetic and a bit of stuff here http://www.haskell.org/haskellwiki/Smart_constructors Cheers, Don (P.S. moved to haskell-cafe(a)haskell.org, more appropriate)

2 1

Re: Why is there no splitBy in the list module?
by tpledger＠ihug.co.nz 13 Jul '06

13 Jul '06

Jared Updike wrote: > > "split" is... unconcatIntersperse. > > How about "separate"? ("split" or "splitBy" is better but it is used > all over the place in many libs) > > And for strings I definitely would use split :: [a] -> [a] -> [[a]] a > lot, just like Python's split function. And "words" works great for > breaking on multiple spaces, so I would avoid trying to fill that > need... FWIW my home-grown versions of these things are called fields and unfields.

4 4

instance Binary Data
by Bulat Ziganshin 12 Jul '06

12 Jul '06

Hello Haskell, one Streams library user asked me about support of serialization TOGETHER with type information which means implementation of "instance Binary Data" (any other variants?). can anyone describe me how i can implement this? Binary instance is very like Show/Read, just uses compact binary encoding of values -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 3

Arrows and 'do' syntax
by Greg Fitzgerald 12 Jul '06

12 Jul '06

I'm trying to translate this HXT code to use the Arrow 'do' syntax: readWriteDoc :: String -> IOSLA (XIOState s) b Int readWriteDoc path = readDocument [(a_validate, "0")] path >>> writeDocument [(a_output_encoding, isoLatin1)] "-" >>> getErrStatus This attempt fails to compile: readWriteDoc :: String -> IOSLA (XIOState s) b Int readWriteDoc = proc path -> do doc <- readDocument [(a_validate, "0")] -< path result <- writeDocument [(a_output_encoding, isoLatin1)] "-" -< doc getErrStatus -< result I get this error message: Couldn't match `(->)' against `IOSLA (XIOState s)' Expected type: t -> t1 Inferred type: IOStateArrow s XmlTree XmlTree Probable cause: `writeDocument' is applied to too many arguments in the call (writeDocument [(a_output_encoding, isoLatin1)] "-") In the command: writeDocument [(a_output_encoding, isoLatin1)] "-" -< doc Any idea what I'm doing wrong? Thanks, Greg

2 2

Re: Haskell-Cafe Digest, Vol 35, Issue 26
by Chad Scherrer 12 Jul '06

12 Jul '06

On 7/12/06, henning thielemann wrote: > There must be an algorithm for finding the minimal spanning tree or > forest. The edges that do not belong to the tree should be the labelled as > cycle-breakers. > Actually, I don't think that would do it, since you could have an acyclic directed graph like this: a -> b | | \/ \/ c -> d There are no cycles here, but the minimal spanning tree is not the whole thing. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Small syntax question
by Maurício 12 Jul '06

12 Jul '06

Hi, I can do this: (let a=3 in a) + (let b=4 in b) but not this: (a where a=3) + (b where b=3) Why? Thanks, Maurício

5 6

Problems installing HDBC-postgresql
by Martin Percossi 12 Jul '06

12 Jul '06

Hi, I'm having problems using HDBC-postgresql (I've tried both 0.99.2.1 and 1.0.0.0) with postgresql (version 8.1.4, installed in /share/pgsql). I adjust the include-dir and extra-lib-dirs to use the custom location of postgresql, and build: no error messages, everything seems fine. However, when I then try to type: ghci -package HDBC -package HDBC-postgresql , I get the error message: Loading package HDBC-postgresql-0.99.2.1 ... linking ... ghc-6.4.2: /home/mpercossi/opt/lib/HDBC-postgresql-0.99.2.1/HSHDBC-postgresql-0.99.2.1.o: unknown symbol `PQserverVersion' ghc-6.4.2: unable to load package `HDBC-postgresql-0.99.2.1' Has anyone seen this error message before? Google didn't turn up anything relevant to haskell -- however there does seem to be a PQserverVersion procedure in the libpq library -- maybe HDBC-postgresql is not seeing this due to the custom install location? TIA Martin

2 2

technique to allow innocuous ambiguity in instance declarations?
by Nicolas Frisby 12 Jul '06

12 Jul '06

Brief disclaimer: I'm using GHC 6.4.1 and haven't looked into Hugs; but I don't suspect there's much difference on this issue. Could easily be wrong there. I've hit a bit of a road bump in ambiguity regarding type class instances and transformer types (in the style of monad transformers). The interesting point is that, in this case, I believe that the ambiguity is harmless and that all possible derivations of instances would be extensionally equivalent. But the typechecker won't let me get far enough to test that hypothesis. So, I have a relation C and intuition that the property can be carried through transformations on either of its related types. I'm seeking 1) a suggested technique for formulating that intuition in such a way that the type-checker could act on it 2) a suggestion claiming that such a harmless ambiguity is down right impossible Below is pseudo-code outlining the shape of my problem. Consider a 2 parameter (both are type constructors) class: > class C f g where > nest :: f a -> g a I have instances for base types (analogous to the Identity monad). > class C IdL IdR where > nest = ... I also have transformers that I can apply to these base types and instances that correspond to "lifting" the C type class property through the transformers. > class C f g => C f (TransR g) where > nest = ... code that involves the "nest" of the C f g instance ... or > class C f g => C (TransL f) g where > nest = ... code that involves the "nest" of the C f g instance ... The simple version of my issue is that, give the instances so far, the compiler won't derive an instance for T. > type T = C (TransL IdL) (TransR IdR) The impasse is the ambiguity in the derivation from C IdL IdR to T. One could apply first TransL or apply first TransR. The "-fallow-overlapping-instances" type system extension fails to help because there is no "most specific" instance. The order of application of my transformers (i.e. transforming the left or transforming the right parameter) does not seem to matter--I have found no intuition that says the derivations ought to be distinguishable in anyway. My question: Is there a technique to allow such innocuous ambiguity in instance declarations? I experimented with introducing something akin to a trace in a third parameter to the class which would disambiguate the derivation (by specifying the order of the transformations; reminded me of "Strongly typed heterogeneous collections"), but had no luck there (perhaps someone else would). Because the ambiguity does not matter to me, I'd be fine implementing a rule such as "always transform the left parameter first", but I don't know how to/if I can formulate that in Haskell. I also tried to reduce the class to a single parameter, which incorporated the the functors into a single type. The method of the class needs those functor types available, so that approach sputtered out. Another issue is modularity: both of my attempts above would have bloated the code using the class with the details needed to disambiguate it. I certainly prefer the context "C f g" to one that exposes the disambiguation. That is, I would highly prefer a solution that allows h1 instead of h2. > h1 :: C f g => a type > h1 = ... some code with nest ... > h2 :: (C f g, DisambiguationHelper f g ?) => a type > h2 = ... some code with nest ... My harrowing suspicion is that I will need to split the property into two--something I can't readily see how to do. Thanks for your time, Nick

2 1