Re: Re: Parsers are monadic?

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: "Read-only" functions in State Monad

Ken Takusagawa wrote:
> I'd like to have a state monad with the feature that I can somehow
> annotate using the type system that some functions are only going to
> read the state and not modify it.  Such read-only functions are only
> permitted to call other read-only functions, whereas state-modifying
> functions can call both read-only and other state-modifying functions.
> 
> How can I do this?  It does not seem to be straightforwardly doable
> with Control.Monad.State.

How about something like

 > readonly :: Reader a -> State a
 > readonly = gets . runReader

Implicit conversion is probably not possible with Control.Monad.State, 
you will have to make your own monad, maybe

 > newtype State2 w s a = State2 (State s a)
 > data Write

The phantom type w can be used to encode whether writing is needed 
(State2 Write) or not (forall w. State2 w)

 > get :: State2 w s s
 > put :: s -> State2 Write s s

Twan

sha1 implementation thats "only" 12 times slower then C

So I tried implementing a more efficient sha1 in haskell, and i got to
about 12 times slower as C.  The darcs implementation is also around
10 to 12 times slower, and the crypto one is about 450 times slower.
I haven't yet unrolled the loop like the darcs implementation does, so
I can still get some improvement from that, but I want that to be the
last thing i do.

I think I've been getting speed improvements when minimizing
unnecessary allocations.  I went from 40 times slower to 12 times
slower by converting a foldM to a mapM that modifies a mutable array.

Anyone have any pointers on how to get hashElem and updateElem to run
faster, or any insight on what exactly they are allocating.  To me it
seems that those functions should be able to do everything they need
to without a malloc.

This is the profiling statistics generated from my implementation

COST CENTRE                    MODULE               %time %alloc

hashElem                       SHA1                  42.9   66.2
updateElem                     SHA1                  12.7   16.7
unboxW                         SHA1                  10.6    0.0
hashA80                        SHA1                   5.2    0.3
temp                           SHA1                   4.6    0.0
sRotateL                       SHA1                   4.6    0.0
ffkk                           SHA1                   3.3    2.6
hashA16IntoA80                 SHA1                   3.1    0.1
sXor                           SHA1                   2.9    0.0
do60                           SHA1                   2.9    2.6
sAdd                           SHA1                   2.3    0.0
do20                           SHA1                   1.3    2.6
splitByN                       SHA1                   1.2    2.3
do80                           SHA1                   0.8    2.6
do40                           SHA1                   0.4    2.6

Thanks,
Anatoly

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: "Read-only" functions in State Monad

Hi Ken,

2007/7/1, Ken Takusagawa <ken.takusagawa.2 <at> gmail.com>:
> I'd like to have a state monad with the feature that I can somehow
> annotate using the type system that some functions are only going to
> read the state and not modify it.

I would suggest declaring a MonadReader instance for State, and
writing your read-only functions as

f :: MonadReader s m => Param -> m Result

Would that solve your problem?

Best,
- Benja

Re: Name Decoration and Undefined References

Bulat Ziganshin-2 wrote:
> 
> Hello SevenThunders,
> 
> Saturday, June 30, 2007, 7:45:57 AM, you wrote:
> 
>> My own code is half Haskell and half C.  My build process is rather
>> complex
> 
> i have the same. initially C code was compiled by gcc but finally i
> switched to ghc-only compilation. it's also important to use the same
> gcc for compiling both Haskell and C code (and using GHC as driver
> solves this problem, of course). i use make to control compilation of
> C code. you can download my program as
> http://www.haskell.org/bz/FreeArc-sources.tar.gz 
> 
> -- 
> Best regards,
>  Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

Yes, I'm in the process of migrating to ghc wherever possible.  For my
little problem, I solved it by copying both the object code (.o files) and
the interface files (.hi files) to the source directory from the object file 
directory created by cabal specifically for building one of my libraries. 
That object code in turn was linked by gcc into another library (foo) with
some external C code.  Then to link against foo in Haskell I make sure it's
compiled with all the .hi files that had been  moved to the source
directory.  Thus you have to control the  files for a given build context
and keep them all together, prior to actually using any libraries or object
files built with that code.  You can't just bring in a different object file
during a previous or different link using ghc.  Unfortunately it's easy
enough to forget where your .hi files came from.

--

-- 
View this message in context: http://www.nabble.com/Name-Decoration-and-Undefined-References-tf4003458.html#a11378399
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Re: sha1 implementation thats "only" 12 times slower then C

aeyakovenko:
> So I tried implementing a more efficient sha1 in haskell, and i got to
> about 12 times slower as C.  The darcs implementation is also around
> 10 to 12 times slower, and the crypto one is about 450 times slower.
> I haven't yet unrolled the loop like the darcs implementation does, so
> I can still get some improvement from that, but I want that to be the
> last thing i do.
> 
> I think I've been getting speed improvements when minimizing
> unnecessary allocations.  I went from 40 times slower to 12 times
> slower by converting a foldM to a mapM that modifies a mutable array.
> 
> Anyone have any pointers on how to get hashElem and updateElem to run
> faster, or any insight on what exactly they are allocating.  To me it
> seems that those functions should be able to do everything they need
> to without a malloc.

Try inlining key small functions, and check the core.

    -O2 -ddump-simpl | less

-- Don

Re: Abstraction leak

Bulat Ziganshin wrote:
> Hello Andrew,
>
> Saturday, June 30, 2007, 11:48:19 AM, you wrote:
>   
>> Well anyway, speed is not my aim. My aim is to play with various 
>> textbook algorithms an examine how well they work for various types of
>> data. As long as the code isn't *absurdly* slow that'll be just fine.
>>     
>
> yes, for studying algorithms Haskell is perfect tool
>
>   
>> (I forget who it was, but a while back somebody pointed out the wisdom
>> of using Data.Map. It certainly makes the LZW implementation about 400%
>> faster! To say nothing of Huffman...)
>>     
>
> it seems that you've done first implementation with lists or immutable
> arrays? :)
>   

Lists.

In fact, I *believe* the code is still on the Wiki somewhere...

>> BTW, how do the pros do Huffman coding? Presumably not by traversing 
>> trees of pointer-linked nodes to process things 1 bit at a time...
>>     
>
> encoding is simple - make this traversal one time and store bit
> sequence for each symbol. for decoding, you can find length of longest
> symbol MaxBits and build table of 2^MaxBits elements which allows to
> find next symbol by direct lookup with next input MaxBits. faster
> algorithms use two-level lookup, first lookup with 9-10 bits is best
> when your encoded symbols are bytes
>   

I see. So build a table of codes and bitmasks and test against that...

Re: Re: Abstraction leak

apfelmus wrote:
> Am I missing something or why wouldn't
>
>   encode, decode :: String -> String
>   encode = encodeRLE . encodeHuffman
>   decode = decodeHuffman . decodeRLE
>
> do the job? This is probably what Andrew intends to do in his Java
> version. Note that this not only RLE-encodes the Huffman table but also
> (needlessly) the data stream. In case you only want to RLE the table, a
> simple Word32 field tracking the size of the Huffman table should be enough.
>   

It is enough. But given that the whole purpose of compression algorithms 
is to squeeze data into the tiniest possible space, I wanted to avoid 
having a size field. And mathematically it's perfectly possible to do... 
I just can't find a convinient way to do it in Haskell. 

Re: Abstraction leak

Andrew Coppin wrote:
> apfelmus wrote:
>> Am I missing something or why wouldn't
>>
>>   encode, decode :: String -> String
>>   encode = encodeRLE . encodeHuffman
>>   decode = decodeHuffman . decodeRLE
>>
>> do the job? This is probably what Andrew intends to do in his Java
>> version. Note that this not only RLE-encodes the Huffman table but also
>> (needlessly) the data stream. In case you only want to RLE the table, a
>> simple Word32 field tracking the size of the Huffman table should be
>> enough.
>>   
> 
> It is enough. But given that the whole purpose of compression algorithms
> is to squeeze data into the tiniest possible space, I wanted to avoid
> having a size field. And mathematically it's perfectly possible to do...
> I just can't find a convinient way to do it in Haskell. 

Well, those 4 bytes won't kill you. But you can of course stop
RLE-decoding as soon as this has read as many bytes as there are in the
Huffman table. A systematic way to do this are parser combinators.

Regards,
apfelmus

Re: Re: Abstraction leak

apfelmus wrote:
> Andrew Coppin wrote:
>   
>>
>> It is enough. But given that the whole purpose of compression algorithms
>> is to squeeze data into the tiniest possible space, I wanted to avoid
>> having a size field. And mathematically it's perfectly possible to do...
>> I just can't find a convinient way to do it in Haskell. 
>>     
>
> Well, those 4 bytes won't kill you. But you can of course stop
> RLE-decoding as soon as this has read as many bytes as there are in the
> Huffman table. A systematic way to do this are parser combinators.
>   

Yeah... I'm fuzzy on how to do this.

I can write parsers to do the various stages, and I can run one parser 
on top of another. But how to you swap whole "stacks" of parsers when 
the top-most one reaches a given stage?