- Haskell-Cafe - Haskell.org

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

13 Jul '06

Jared Warren wrote: > Haskell's type checking language is a logical programming language. > The canonical logical language is Prolog. > Why can't Haskell (with extensions) do type-level Peano naturals in > the same fashion? The code would be something like: Also of possible interest, _Fun with Functional Dependencies_... http://www.cs.chalmers.se/~hallgren/Papers/wm01.html "This paper illustrates how Haskell's type class system can be used to express computations. Since computations on the type level are performed by the type checker, these computations are static (i.e., performed at compile-time), and, since the type system is decidable, they always terminate. Haskell thus provides a means to express static computations, and has a clear distinction between static and dynamic computations. "

1 0

Comma in the front
by Joel Reymont 13 Jul '06

13 Jul '06

Are cool kids supposed to put the comma in front like this? , foo , bar , baz Is this for historical or other reasons because Emacs formats Haskell code well enough regardless. Thanks, Joel -- http://wagerlabs.com/

6 7

Haskore dependency trouble
by Yitzchak Gale 13 Jul '06

13 Jul '06

I am having trouble installing Haskore due to a dependency issue. I am a pampered user of Debian. Thanks to wonderful work by the Cabal people and the Debian package maintainers, I have never had to use Cabal manually to install a package before. In order to learn how to do that, I practiced by installing the ever-important HNOP package. After a few tries, I found that the following sequence of commands works: ./Setup.hs configure --prefix=/usr ./Setup.hs build sudo ./Setup.hs install But similar commands for Haskore do not fair as well. The configure command fails with the following error: Setup.lhs: cannot satisfy dependency Hsc-any How can I satisfy that dependency? I am using ghc on Debian testing. I obtained Haskore from http://cvs.haskell.org/darcs/haskore Thanks! Incidentally, why is Cabal not smart enough to know that with ghc on linux the default prefix is /usr? -Yitz

5 10

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