Re: [Haskell-cafe] Performance of delete-and-return-last-element
Am 31.08.13 14:35, schrieb Petr Pudlák:
One solution would be to fold over a specific semigroup instead of a
recursive function:
|import Data.Semigroup
import Data.Foldable(foldMap)
import Data.Maybe(maybeToList)
data Darle a =Darle {getInit :: [a],getLast ::a }
deriving Show
instance Semigroup (Darle a)where
~(Darle xs1 l1) ~(Darle xs2 l2) =Darle (xs1 ++ [l1] ++ xs2) l2
darle :: [a] -Darle a
darle = foldr1 () . map (Darle [])|
It's somewhat more verbose, but the core idea is clearly expressed in
the one line that defines ||, and IMHO it better shows /what/ are we
doing rather than /how/. It's sufficiently lazy so that you can do
something like |head . getInit $ darle [1..]|.
I am wondering why you put the Semigroup instance there and what the
other imports are for. Doesn't this work just as well?
data Darle a = Darle {getInit :: [a], getLast :: a}
deriving Show
~(Darle xs1 l1) ~(Darle xs2 l2) = Darle (xs1 ++ [l1] ++ xs2) l2
darle :: [a] -Darle a
darle = foldr1 () . map (Darle [])
Seems to work here. I am still puzzled, though, if this is really a good
idea performance-wise. I am afraid I don't understand it well enough.
Harald
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Either example
Am 07.02.13 03:37, schrieb Jacob Thomas:
Hello
I'm new to Haskell, and need help with figuring out the Either type...
Any example to show how this works?
Maybe a program I wrote a while ago can help you get it.
https://github.com/ctbo/slitherlink
In Slitherlink.hs there is a function readProblem that can fail. It
returns either a String with an error message (Left) or the problem read
(Right).
[...]
readProblem :: String - Either String Problem
readProblem s = do
pl - readProblemList s
when (null pl) $ Left Problem is empty.
let columns = length $ head pl
when (columns == 0) $ Left Problem starts with an empty line.
unless (all ((== columns) . length) pl) $ Left Problem not
rectangular.
let rows = length pl
return $ listArray ((0, 0), (rows-1, columns-1)) $ concat pl
[...]
Or if you don't feel comfortable with using the Either monad, look at
the even simpler function readConstraint a few lines earlier in the same
file.
In the main solve.hs program this is used to output a meaningful error
message to the user if the input file is invalid:
[...]
where work s n = case readProblem s of
Left e - putStrLn e
Right p - do
[...do something with the problem p...]
Hope this helps.
Harald
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Problems updating cabal-install on Mac OS
Hi Cafe,
I just installed the brand new Haskell Platform 2012.4.0.0 for Mac OS X,
32 bit, after removing everything left over from the old one (I hope).
Next I started cabal which said to me:
Downloading the latest package list from hackage.haskell.org
Note: there is a new version of cabal-install available.
To upgrade, run: cabal install cabal-install
So next I did
cabal install cabal-install
which started working
Resolving dependencies...
Downloading Cabal-1.16.0.2...
and finished with
Installing executable(s) in
/Users/bo/Library/Haskell/ghc-7.4.2/lib/cabal-install-1.16.0.1/bin
Updating documentation index /Users/bo/Library/Haskell/doc/index.html
When I then tried
cabal update
it still said
Downloading the latest package list from hackage.haskell.org
Note: there is a new version of cabal-install available.
To upgrade, run: cabal install cabal-install
I thought I just had done that. What could have gone wrong?
Haralds-iMac:~ bo$ which cabal
/Users/bo/Library/Haskell/bin/cabal
Haralds-iMac:~ bo$ ls -l `which cabal`
lrwxr-xr-x 1 bo staff 49 6 Nov 18:15 /Users/bo/Library/Haskell/bin/cabal
- ../ghc-7.4.2/lib/cabal-install-1.16.0.1/bin/cabal
Now that I am writing this up I am noticing that the last thing that
seems to be installed has version number 1.16.0.1, while it started out
with 1.16.0.2.
So on a second thought I am attaching the full log of the install.
Am I doing anything wrong?
Harald
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
Haralds-iMac:~ bo$ echo $PATH
/Users/bo/Library/Haskell/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/bin:/opt/X11/bin
Haralds-iMac:~ bo$ cabal install cabal-install
Resolving dependencies...
Downloading Cabal-1.16.0.2...
[ 1 of 65] Compiling Distribution.Compat.Exception (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Compat/Exception.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Compat/Exception.o
)
[ 2 of 65] Compiling Distribution.Compat.TempFile (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Compat/TempFile.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Compat/TempFile.o
)
[ 3 of 65] Compiling Distribution.Compat.CopyFile (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Compat/CopyFile.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Compat/CopyFile.o
)
[ 4 of 65] Compiling Distribution.GetOpt (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/GetOpt.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/GetOpt.o
)
[ 5 of 65] Compiling Distribution.Compat.ReadP (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Compat/ReadP.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Compat/ReadP.o
)
[ 6 of 65] Compiling Distribution.Text (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Text.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Text.o
)
[ 7 of 65] Compiling Distribution.Version (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/Version.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Distribution/Version.o
)
[ 8 of 65] Compiling Language.Haskell.Extension (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Language/Haskell/Extension.hs,
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/dist/setup/Language/Haskell/Extension.o
)
[ 9 of 65] Compiling Distribution.TestSuite (
/var/folders/z6/bwzyx17111b33phycyx91754gn/T/Cabal-1.16.0.2-24584/Cabal-1.16.0.2/Distribution/TestSuite.hs
Re: [Haskell-cafe] Problems updating cabal-install on Mac OS
Am 06.11.12 18:46, schrieb Brandon Allbery:
On Tue, Nov 6, 2012 at 12:27 PM, Harald Bögeholz b...@ct.de wrote:
When I then tried
cabal update
it still said
Downloading the latest package list from hackage.haskell.org
Did you do hash -r so your shell will forget that it had already found
cabal in /usr/bin?
(This is not a Mac OS X thing, it's a bash and zsh thing. csh/tcsh does it
too but you clear its path hash table with rehash.)
Oops, you are right! Now it seems to work, stupid me!
I thought that by issuing these two commands
Haralds-iMac:~ bo$ which cabal
/Users/bo/Library/Haskell/bin/cabal
Haralds-iMac:~ bo$ ls -l `which cabal`
lrwxr-xr-x 1 bo staff 49 6 Nov 18:15
/Users/bo/Library/Haskell/bin/cabal -
../ghc-7.4.2/lib/cabal-install-1.16.0.1/bin/cabal
I had made sure I was using the new version. But apparently not!
Thanks a lot!
(I still find it mildly confusing that there are two different version
numbers involved:
Haralds-iMac:~ bo$ cabal --version
cabal-install version 1.16.0.1
using version 1.16.0.2 of the Cabal library
but that seems to be ok?)
Harald
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] progress reporting in a backtracking algorithm
Dear Haskell Cafe,
I am playing around with a backtracking algorithm that can take quite a
while to compute all solutions to a problem.
I'd like to use Debug.Trace.trace to provisionally output something that
lets me estimate the total time it might take. But I just can't wrap my
head around it.
This is how I think I'd write it in a C-like language:
backtrack(int level, double position, double stepsize, misc...)
{
// with variations = number of variations to try on this level
double part = stepsize / variations // split time on this level
for (i=0; ivariations; ++i)
{
double current = position + part*i
// do the actual work
backtrack(level+1, current, part);
if (level not_too_much_detail)
printf(progress: %f%%\n, current);
}
}
and start with backtrack(1, 0.0, 100.0).
And now for something completely Haskell:
I have a function
step :: State - Index - [State]
that on a certain level tries all allowable varaiants and returns a list
of those that can be further pursued on deeper levels.
Then solving the problem involves applying the step on all levels
(whicht are indexed by some array indices here):
solve :: Problem - [State]
solve problem = foldM step start grid
where start = stateFromProblem problem
grid = indices (sLines start)
I am totally at loss at how I could accomplish some kind of progress
reporting in this lazily evaluated (I hope) backtracking scheme.
If anybody would like to review the full code (about 80 lines total vor
the solver, not counting I/O), this is where I am right now:
https://github.com/ctbo/slitherlink/tree/c8951ca1eaf83ce9de43f0483740ce339f4134ae
and this is the branch I am working on right now:
https://github.com/ctbo/slitherlink/tree/2lines
Or is there maybe a totally different and better way to approach this
kind of tree search in Haskell? I'm eager to learn.
Thanks for your attention
Harald
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] performance issues with popCount
Dear Haskell Cafe,
I am struggling with the performance of the popCount function from
Data.Bits.
To be more precise: I downloaded the Haskell Platform 2012.2.0.0 from
http://hackage.haskell.org/platform/ (64 bit, Mac OS X). In this version
I found the popCount function to be broken. If I look in the online
documentation at
http://hackage.haskell.org/packages/archive/base/4.5.1.0/doc/html/src/Data-Bits.html#popCount
it is already fixed, but included with my Haskell Platform was the
broken version.
Anyway, I tried this version
popCount :: Integer - Int
popCount = go 0
where
go c 0 = c
go c w = go (c+1) (w .. (w - 1))
and profiling showed that my program spent 80 % of its time counting bits.
So I thought I'm clever and implement a table-based version like this:
popCount' :: Integer - Int
popCount' = go 0
where
go c 0 = c
go c w = go (c+1) (w .. (w - 1))
popCountN = 10
popCountMask :: Integer
popCountMask = shift 1 popCountN - 1
popCountTable :: Array Integer Int
popCountTable = listArray (0, popCountMask) $ map popCount' [0 ..
popCountMask]
popCount :: Integer - Int
popCount 0 = 0
popCount x = popCountTable ! (x .. popCountMask) + popCount (x `shiftR`
popCountN)
turns out this is even slower ... now my program spends 90 % of its time
counting bits :-(.
Any hints?
Thanks
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Asking for advice on programming style and also performance
Dear Haskell Cafe,
I am working on a solver for Slitherlink puzzles in Haskell. Today I am
completely puzzled that a small change I made had a huge performance
impact. I thought the change to be merely cosmetic to make a function a
little more elegant and the code more readable. But this change slowed
down my program by a factor of 100!
I would greatly appreciate advice from experienced Haskellers why this
has happened. The program is hosted on github; this is the direct link
to the change with unexpected outcome:
https://github.com/ctbo/slitherlink/commit/b6f58699258ef68ddee21a1346bd184465aaaba2
The program itself isn't commented at all, but I have written a sketch
of how it works in the wiki:
https://github.com/ctbo/slitherlink/wiki/How-it-works
While I am at it:
I would also appreciate any advice you might have on the programming
style in general. I am relatively new to Haskell and this is my first
nontrivial program. So any suggestions for improvements are welcome!
Thanks for your time,
--
Harald Bögeholzb...@ct.de (PGP key available from servers)
Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417
http://www.ct.de/
int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
main(){for(;b=c,c-=14;i=printf(%04d,e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
(Arndt/Haenel)
Affe Apfel Vergaser
/* Heise Zeitschriften Verlag GmbH Co. KG * Karl-Wiechert-Allee 10 *
30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
