Send Beginners mailing list submissions to
        [email protected]

To subscribe or unsubscribe via the World Wide Web, visit
        http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
        [email protected]

You can reach the person managing the list at
        [email protected]

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."


Today's Topics:

   1.  Red-Black Tree Library in Haskell (Jimmy Wylie)
   2.  editing a list (Jonathan Phillips)
   3. Re:  Red-Black Tree Library in Haskell (Johan Tibell)
   4. Re:  Red-Black Tree Library in Haskell (Johan Tibell)
   5. Re:  editing a list (Brent Yorgey)
   6. Re:  editing a list (Daniel Fischer)
   7. Re:  Red-Black Tree Library in Haskell (Jimmy Wylie)
   8. Re:  Red-Black Tree Library in Haskell (Stephen Tetley)


----------------------------------------------------------------------

Message: 1
Date: Tue, 2 Nov 2010 14:18:05 -0500
From: Jimmy Wylie <[email protected]>
Subject: [Haskell-beginners] Red-Black Tree Library in Haskell
To: <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="UTF-8"; format=flowed

Hi,

I'm looking for a Red-Black Tree implementation in Haskell.  I could 
have sworn I saw it on hackage somewhere, but now I can' t seem to find it.

Does anyone know where I could find an implementation of it? ( I guess I 
could roll my own, but I'd rather just use a library).

Thanks,
Jimmy



------------------------------

Message: 2
Date: Sat, 30 Oct 2010 15:59:00 +0100
From: Jonathan Phillips <[email protected]>
Subject: [Haskell-beginners] editing a list
To: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

I have a list (more precisely a string) which I'm trying to recurse
through, editing sections as I come to it.  It's obvious how to do it
with a for loop, but I'm doing it all wrong in haskell, as this simple
task is running mind-numbingly slowly.

addOneNum cycles through each line, and when it gets to character 23,
it calls changeNo, which edits the string.  The problem is clearly the
adding on to the end of the string, but the only other way I can see
of doing it is writing the 'new string' backwards and then reverse it
at the end.  This looks like it would make the function even less
legible than it already is though.


addOneNum       :: String -> String -> Integer -> String

addOneNum x [] _        = x
addOneNum x (y:ys) n    = case n of
        23      -> changeNo x (y:ys) n
        _       -> case y of
                '\n'    -> addOneNum (x ++ [y]) ys 1
                _       -> addOneNum (x ++ [y]) ys (n+1)

changeNo        :: String -> String -> Integer -> String
changeNo v (w:x:y:z:xs) n       = case
length(show((read([w,x,y,z])::Integer) + 1)) of
        0 -> addOneNum (v ++ "    ") xs (n+4)
        1 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
  ") xs (n+4)
        2 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
 ") xs (n+4)
        3 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
") xs (n+4)
        4 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1)) xs (n+4)
        _ -> error "asdf"
changeNo w _ n  = error "changeNo error"


Also, while I'm at it, it looks like I want to be using an as-pattern
(or some C-style #define thing):

changeNo v (w:x:y:z:xs) n       = case
length(s@(show((read([w,x,y,z])::Integer) + 1))) of
        0 -> addOneNum (v ++ "    ") xs (n+4)
        1 -> addOneNum (v ++ s ++ "   ") xs (n+4)
        2 -> addOneNum (v ++ s ++ "  ") xs (n+4)
        3 -> addOneNum (v ++ s ++ " ") xs (n+4)
        4 -> addOneNum (v ++ s) xs (n+4)
        _ -> error "asdf"

but that gives me a 'not in scope' error.  Any suggestions?

Cheers,
PhiJ


------------------------------

Message: 3
Date: Tue, 2 Nov 2010 20:37:04 +0100
From: Johan Tibell <[email protected]>
Subject: Re: [Haskell-beginners] Red-Black Tree Library in Haskell
To: Jimmy Wylie <[email protected]>
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Nov 2, 2010 at 8:18 PM, Jimmy Wylie <[email protected]> wrote:
> I'm looking for a Red-Black Tree implementation in Haskell.  I could have
> sworn I saw it on hackage somewhere, but now I can' t seem to find it.

Didn't Milan Straka benchmark one in his containers package?

Johan


------------------------------

Message: 4
Date: Tue, 2 Nov 2010 20:37:50 +0100
From: Johan Tibell <[email protected]>
Subject: Re: [Haskell-beginners] Red-Black Tree Library in Haskell
To: Jimmy Wylie <[email protected]>
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Nov 2, 2010 at 8:37 PM, Johan Tibell <[email protected]> wrote:
> On Tue, Nov 2, 2010 at 8:18 PM, Jimmy Wylie <[email protected]> wrote:
>> I'm looking for a Red-Black Tree implementation in Haskell.  I could have
>> sworn I saw it on hackage somewhere, but now I can' t seem to find it.
>
> Didn't Milan Straka benchmark one in his containers package?

That's containers *paper*:

http://research.microsoft.com/~simonpj/papers/containers/containers.pdf


------------------------------

Message: 5
Date: Tue, 2 Nov 2010 15:43:48 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] editing a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii

Can you give a few simple examples of some typical inputs and outputs
for your functions?  There are almost certainly much better ways to do
whatever you are trying to do, but I am having trouble understanding
exactly what it is.

-Brent

On Sat, Oct 30, 2010 at 03:59:00PM +0100, Jonathan Phillips wrote:
> I have a list (more precisely a string) which I'm trying to recurse
> through, editing sections as I come to it.  It's obvious how to do it
> with a for loop, but I'm doing it all wrong in haskell, as this simple
> task is running mind-numbingly slowly.
> 
> addOneNum cycles through each line, and when it gets to character 23,
> it calls changeNo, which edits the string.  The problem is clearly the
> adding on to the end of the string, but the only other way I can see
> of doing it is writing the 'new string' backwards and then reverse it
> at the end.  This looks like it would make the function even less
> legible than it already is though.
> 
> 
> addOneNum       :: String -> String -> Integer -> String
> 
> addOneNum x [] _        = x
> addOneNum x (y:ys) n    = case n of
>         23      -> changeNo x (y:ys) n
>         _       -> case y of
>                 '\n'    -> addOneNum (x ++ [y]) ys 1
>                 _       -> addOneNum (x ++ [y]) ys (n+1)
> 
> changeNo        :: String -> String -> Integer -> String
> changeNo v (w:x:y:z:xs) n       = case
> length(show((read([w,x,y,z])::Integer) + 1)) of
>         0 -> addOneNum (v ++ "    ") xs (n+4)
>         1 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
>   ") xs (n+4)
>         2 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
>  ") xs (n+4)
>         3 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
> ") xs (n+4)
>         4 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1)) xs (n+4)
>         _ -> error "asdf"
> changeNo w _ n  = error "changeNo error"
> 
> 
> Also, while I'm at it, it looks like I want to be using an as-pattern
> (or some C-style #define thing):
> 
> changeNo v (w:x:y:z:xs) n       = case
> length(s@(show((read([w,x,y,z])::Integer) + 1))) of
>         0 -> addOneNum (v ++ "    ") xs (n+4)
>         1 -> addOneNum (v ++ s ++ "   ") xs (n+4)
>         2 -> addOneNum (v ++ s ++ "  ") xs (n+4)
>         3 -> addOneNum (v ++ s ++ " ") xs (n+4)
>         4 -> addOneNum (v ++ s) xs (n+4)
>         _ -> error "asdf"
> 
> but that gives me a 'not in scope' error.  Any suggestions?
> 
> Cheers,
> PhiJ
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners


------------------------------

Message: 6
Date: Tue, 2 Nov 2010 21:10:53 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] editing a list
To: [email protected]
Cc: Jonathan Phillips <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain;  charset="iso-8859-1"

On Saturday 30 October 2010 16:59:00, Jonathan Phillips wrote:
> I have a list (more precisely a string) which I'm trying to recurse
> through, editing sections as I come to it.  It's obvious how to do it
> with a for loop, but I'm doing it all wrong in haskell, as this simple
> task is running mind-numbingly slowly.
>
> addOneNum cycles through each line, and when it gets to character 23,
> it calls changeNo, which edits the string.  The problem is clearly the
> adding on to the end of the string,

Yes, that's bad, since the parentheses nest the wrong way. You get

((((a ++ b) ++ c) ++ d) ++ e)

and to get to the start, you have to dig through all those layers of 
parentheses. It would be less bad if the construction built right-nested 
parentheses.

> but the only other way I can see
> of doing it is writing the 'new string' backwards and then reverse it
> at the end.  This looks like it would make the function even less
> legible than it already is though.

It's a fairly common technique, since consing to the front of a list is 
very cheap while appending to the end is expensive (especially if you 
repeatedly add single elements).

However, here you can get much better behaviour by using another common 
technique, delivering the string incrementally.

Since all you ever do with the accumulator is appending to the end of it, 
you don't need an accumulator at all.

>
>
> addOneNum       :: String -> String -> Integer -> String
>
> addOneNum x [] _        = x
> addOneNum x (y:ys) n    = case n of
>         23      -> changeNo x (y:ys) n
>         _       -> case y of
>                 '\n'    -> addOneNum (x ++ [y]) ys 1
>                 _       -> addOneNum (x ++ [y]) ys (n+1)

addOneNum' :: String -> Integer -> String
addOneNum' [] _ = []
addOneNum' (y:ys) n =
  case n of
    23 -> changeNo' (y:ys) n
    _  -> case y of
            '\n' -> y : addOneNum' ys 1
            _    -> y : addOneNum' ys (n+1)

changeNo' :: String -> Integer -> String
changeNo' (w:x:y:z:xs) n =
  let s = show ((read [w,x,y,z] :: Integer) + 1)
  in case length s of
        0 -> "    " ++ addOneNum' xs (n+4)  -- can't happen, by the way
        l | l < 4 -> s ++ "    " ++ addOneNum' xs (n+4)
           -- guessing it's the same number of spaces for those
          | otherwise -> error "asdf"
changeNo' _ _ = error "changeNo' error"

If the input is incrementally produced and the output sequentially 
consumed, that runs in constant space (and if not all output is needed, 
it'll stop early).

>
> changeNo        :: String -> String -> Integer -> String
> changeNo v (w:x:y:z:xs) n       = case
> length(show((read([w,x,y,z])::Integer) + 1)) of
>         0 -> addOneNum (v ++ "    ") xs (n+4)
>         1 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
>   ") xs (n+4)
>         2 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
>  ") xs (n+4)
>         3 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1) ++ "
> ") xs (n+4)
>         4 -> addOneNum (v ++ show((read([w,x,y,z])::Integer) + 1)) xs
> (n+4) _ -> error "asdf"
> changeNo w _ n  = error "changeNo error"
>
>
> Also, while I'm at it, it looks like I want to be using an as-pattern
> (or some C-style #define thing):
>
> changeNo v (w:x:y:z:xs) n       = case
> length(s@(show((read([w,x,y,z])::Integer) + 1))) of
>         0 -> addOneNum (v ++ "    ") xs (n+4)
>         1 -> addOneNum (v ++ s ++ "   ") xs (n+4)
>         2 -> addOneNum (v ++ s ++ "  ") xs (n+4)
>         3 -> addOneNum (v ++ s ++ " ") xs (n+4)
>         4 -> addOneNum (v ++ s) xs (n+4)
>         _ -> error "asdf"
>
> but that gives me a 'not in scope' error.  Any suggestions?

You can use as-patterns only in pattern-matching contexts. You could write

case show (...) of
  s -> case length s of
        0 -> ...

but normally you bind the value to the name via a let (or where).

>
> Cheers,
> PhiJ



------------------------------

Message: 7
Date: Tue, 2 Nov 2010 15:35:38 -0500
From: Jimmy Wylie <[email protected]>
Subject: Re: [Haskell-beginners] Red-Black Tree Library in Haskell
To: Johan Tibell <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="ISO-8859-1"; format=flowed

On 11/2/10 2:37 PM, Johan Tibell wrote:
> On Tue, Nov 2, 2010 at 8:37 PM, Johan Tibell<[email protected]>  wrote:
>> On Tue, Nov 2, 2010 at 8:18 PM, Jimmy Wylie<[email protected]>  wrote:
>>> I'm looking for a Red-Black Tree implementation in Haskell.  I could have
>>> sworn I saw it on hackage somewhere, but now I can' t seem to find it.
>> Didn't Milan Straka benchmark one in his containers package?
> That's containers *paper*:
>
> http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
>
>
It looks like in that paper, they implemented their own Red-Black 
Tree-based Set, which isn't provided on hackage.  It also doesn't look 
like they uploaded that implementation either.

I guess I could use an AVL Tree, but I think a Red-Black Tree provides 
better insertion times, which is important for my program.

Thanks for the help,
Jimmy



------------------------------

Message: 8
Date: Tue, 2 Nov 2010 21:49:01 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Red-Black Tree Library in Haskell
Cc: [email protected]
Message-ID:
        <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1

Ralf Hinze has a paper Constructing Red-Black Trees which is cached on Citeseer

http://www.comlab.ox.ac.uk/people/publications/date/Ralf.Hinze.html
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2171

I thought someone turned the implementation in the paper into a
library on Hackage, but I can't find it either.


------------------------------

_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners


End of Beginners Digest, Vol 29, Issue 3
****************************************

Reply via email to