December 2009 - Haskell-Cafe

Beginner's speed problem
by Aditya M 03 Dec '09

03 Dec '09

Hi, I am trying to solve this problem: https://www.spoj.pl/problems/LASTDIG/ It is very simple. Given a and b, return the last digit of a^b. b could be large, so I used logarithmic exponentiation and wrote/submitted the code below for this problem: ---------------------------------------------------------------------- lastdigit :: Int -> Int -> Int -> Int lastdigit 0 0 _ = 1 lastdigit a b c | even b = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) c | b == 1 = (a*c) `rem` 10 | otherwise = lastdigit ( (a*a) `rem` 10 ) (b `quot` 2) (a*c) doit :: [Char] -> Int doit line = lastdigit (read $ head $ words line) (read $ last $ words line) 1 main = do n <- getLine inputs <- sequence $ take (read n) $ repeat getLine let slist = map doit inputs mapM_ (putStrLn.show) slist ------------------------------------------------------------------- As n in main is at most 30, I thought this would easily run in 1 second, but I get a time limit exceeded error on the site. Can someone tell me where my code is taking too much time? Thanks in advance! -- Aditya Manthramurthy

3 4

Data.Binary and error handling
by Alexey Khudyakov 03 Dec '09

03 Dec '09

Hello Is there any plans to add error handling for binary? When it comes to binary parsing most awkward part is error handling I presume answer will be like "there are some vague plans but no one to implement them" so the second question how could it be done? Naive implementation of error handliing which converts Get monad into hybrid of state monad and error monad (Either like) gives about 5 times slowdown.

6 9

Card games
by Felipe Lessa 03 Dec '09

03 Dec '09

Hi! I would like to know if anybody has already thought of or tried to code an EDSL for card games. Ideally you should be able to write the rules the games and get "for free": - Game generator: given an input deck, construct the initial state of the game. - Random game generator: besides just creating a random deck and using the item above, it should be nice to be able to randomly construct the game from the final positions. This should guarantee that all random games are solvable. - "Hints" generator: IOW list possible moves given a game state. - Playable game: probably the EDSL should include at least some information to be able to properly place the cards on the screen. - Game solver: this is somewhat harder to do efficiently, but an inneficient one should be doable. - Demo mode: related to the above, an auto-play distract-me mode. - Tutorial mode: show a screen for each of the rules written? - ...anything more? Just curious, this looks like a perfect job for an EDSL. Also, I guess anybody trying to do something like this should read PySol's code to have some ideas. -- Felipe.

6 12

Fwd: [Haskell-cafe] Optimization with Strings ?
by Alberto G. Corona 03 Dec '09

03 Dec '09

Use makeStableName from System.Mem.StableName StableName`s are just for checking pointer equality. Instead of checking for equality of the strings, check for pointer equality of their stableNames a dirty way: pointerEq x y= unsafePerformIO $ do px <- makeStableName x py <- makeStableName y return x == y pEq x y | pointerEq x y == True = True | otherwise = x == y 2009/12/3 David Virebayre <dav.vire+haskell(a)gmail.com<dav.vire%2Bhaskell(a)gmail.com> > On Thu, Dec 3, 2009 at 1:03 PM, Emmanuel CHANTREAU > <echant+haskell(a)maretmanu.org <echant%2Bhaskell(a)maretmanu.org>> wrote: > > > In my futur program, it use a lot of binary trees with strings (words) > > as leaf. There is just arround 1000 words and they will appear a lot of > > times. The program will possibly consume a lot of process and memory > > (it is a mathematics proover). > > > I began this program in C++ but haskell has a prety good speed and > > memory footprint and is easier. But I don't know if it worth to do this > > optimization: having a dictionary to translate string words in Int. > > > The answer depends on the automatic optimizations in GHC, because GHC > > could compare quickely two strings if it is the same object, so it > > depends if program generated by GHC have a dictionary (tree) of strings > > internaly. Someone knows this ? > > It doesn't work this way : Strings are just lists of Chars. Comparison > is made recursively, Char by Char. You can have a look at the source > to make sure : > > instance (Eq a) => Eq [a] where > [] == [] = True > (x:xs) == (y:ys) = x == y && xs == ys > _xs == _ys = False > > So you will have to code your own optimisation. > > David. > > P.S. In French if you didn't understand: > > Ca ne marche pas comme ça. > Les chaines de caractères ne sont que des listes de caractères. > La comparaison sur les listes est faite récursivement, caractère par > caractère, il suffit pour s'en assurer de regarder au source : > Donc il vaut mieux que tu implémente ton propre dictionnaire. > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Re: [Haskell-cafe] Existencial Types
by rodrigo.bonifacio 03 Dec '09

03 Dec '09

Dear Luke, thanks for your answers.... > If SelectScecario is used for other purposes, then give an explicit > cast function Sure, as I mentioned, we have different transformations and it would be worth to filter a list of transformations by a particular type or even apply the list of transformations in a particular order considering their type. > toTransformation :: SelectScenario -> Transformation > toTransformation (SelectScenario ids) = Transformation { > (<+>) = {- implementation of (<+>) just as if it were a class method -} > } I understand your idea, but I will have to implement several variations of "toTransformation", one for each kind of transformation. Moreover, I couldn't realize how is possible to define a function that could be applied to different transformations without using type classes--- I have to restrict the types of argument of such a function. Moreover, I couldn't figure out what are the benefits of your solution. Please, if possible, could you elaborate that a bit more, in order that I could understand why your design is better (I mean, more legible, reusable or concise)? Thanks in advance, Rodrigo. Em 01/12/2009 22:44, Luke Palmer < lrpalmer(a)gmail.com > escreveu: On Tue, Dec 1, 2009 at 4:21 PM, rodrigo.bonifacio wrote: > Thanks Luke. > > In fact I, will have different implementations of the Transformation type. > Something like: > > data SelectScenarios = SelectScenarios { > > scIds :: [Id] > > } What is this different type buying you? You can never "downcast" to it later. > And then I should be able to make SelectScenarios a kind of Transformation. > So I think that I really need a class. What do you think about it? > > instance Transformation SelectScenario where > > (<+>) .... So instead of making a type and an instance, just implement it directly as a Transformation: selectScenario :: [Id] -> Transformation selectScenario ids = Transformation { (<+>) = {- whatever implementation you gave for (<+>) above, using ids -} } If the only purpose of SelectScenario (your type) is to be used polymorphically as a Transformation, then this approach is isomorphic -- i.e. anything you can do with the existential type trick you can do with this approach. If SelectScecario is used for other purposes, then give an explicit cast function toTransformation :: SelectScenario -> Transformation toTransformation (SelectScenario ids) = Transformation { (<+>) = {- implementation of (<+>) just as if it were a class method -} } Existential types only buy you power when the quantified variable appears more than once on the right hand side, for example: forall a. Num a => (a,a). But even those can usually be factored out into more direct representations (I seem to recall Oleg has a proof that they always can, actually). Luke

1 0

Re: seems like I'm on the wrong track
by John Lato 03 Dec '09

03 Dec '09

> From: Henning Thielemann <lemming(a)henning-thielemann.de> > > Michael P Mossey schrieb: >> Perhaps someone could either (1) help me do what I'm trying to do, or >> (2) show me a better way. >> >> I have a problem that is very state-ful and I keep thinking of it as OO, >> which is driving me crazy. Haskell is several times harder to use than >> Python in this instance, probably because I'm doing it wrong. >> >> To give you a larger context, this problem is essentially compiling a >> description of music (my own) into a kind of music-machine-language >> (CSound). CSound is relatively untidy. > > There are currently two public interfaces to CSound: > > http://hackage.haskell.org/packages/archive/haskore/0.1/doc/html/Haskore-In… > > http://hackage.haskell.org/package/hCsound > Incidentally, these two packages serve very different purposes. hCsound is an interface to the Csound runtime API, while the Haskore interface is an EDSL front-end to Csound's own input format. There is very little overlap in functionality between the two. The Haskore interface is much closer to what Michael wants to do, but as he's commented already, it is a bit dated. hCsound is unlikely to be of much use for compiling a secondary language to csound code. John

1 0

Re: [Haskell-cafe] Is Haskell a Fanatic?
by John D. Earle 03 Dec '09

03 Dec '09

It will be better for all of you to figure it out for yourselves and gain more experience about what is out there. Haskell isn't the world. Haskell would be the cutting edge if it didn't have competition.

2 1

Re: [Haskell-cafe] Implicit newtype unwrapping
by John D. Earle 03 Dec '09

03 Dec '09

There is another point that needs to be made. A type signature isn't actually a type specification. It is a type assertion and a type specification in the event that the compiler needs your help. Most of the time the compiler can care less what you think and does not require your assistance. In languages like C you get to call the shots. In languages such as Haskell you don't get that opportunity.

1 0

[Fwd: Re: [Haskell-cafe] Implicit newtype unwrapping]
by Holger Siegel 03 Dec '09

03 Dec '09

Am Donnerstag, den 03.12.2009, 01:16 +0100 schrieb Martijn van Steenbergen: > So here's a totally wild idea Sjoerd and I came up with. > > What if newtypes were unwrapped implicitly? > > What advantages and disadvantages would it have? > In what cases would this lead to ambiguous code? 1) instance Monoid a => Monoid (Dual a) 2) instance Monoid (Endo a) instance Monoid b => Monoid (a -> b)

3 4

Some help needed to start Haskell with Yi
by Jaco van Iterson 03 Dec '09

03 Dec '09

Hi there I'm new to Haskell and need some help to get started faster (busy busy busy). I like to adjust and extend an editor to my liking and I choose Yi. Only installation with 'cabal install yi' in a Cygwin shell under MS Windows XP ended in: Yi\Prelude.hs:182:9: Duplicate instance declarations: instance Category Accessor.T -- Defined at Yi\Prelude.hs:182:9-38 instance Category Accessor.T -- Defined in data-accessor-0.2.1:Data.Accessor.Private cabal.exe: Error: some packages failed to install: yi-0.6.1 failed during the building phase. The exception was: exit: ExitFailure 1 :( Seems easy to fix but I can't even find where on my drive I can find the source code. Where is the source? Cheers, Jaco

13 26