June 2015 - Beginners

Dynamic programming (memoization) w/ string keys.
by Sourabh 07 Jun '15

07 Jun '15

Hello again! I'm hoping to get some more insight into another memoization issue I'm facing. This time, I was solving the following problem, which seems like a dynamic programming problem. https://www.hackerrank.com/challenges/game-of-kyles I coded up a straightforward recurrence equation (without any memoization): https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalP… The function playGameOfKyles shows the recurrence. (playGameOfKyles :: String -> Bool) I tried to perform top-down dynamic programming, by caching the results in a Data.Map, in between calls to the function. This is because the input is a string. Here is the new version: https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalP… Basically I am passing a map around, and returning one as well. ( playGameOfKyles :: CacheMap -> String -> (Bool, CacheMap)) The naive version (without memoization) is extremely slow of course, and probably won't finish running until the sun cools down (so far, even one test case of a string with length 74 hasn't finished running after many minutes). The memoized version is... improving something... and for example the entire test case 2, which contains 100 test cases of size 50 to 100 each, runs in about 8 minutes. Is there something I can improve with the memoization, to make it faster? Use something other than Data.Map? Or could the bottleneck be someplace else in the algorithm? I know those are kinda broad questions, but I've run out of ideas...

2 1

Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata
by Sourabh 07 Jun '15

07 Jun '15

Thanks for the wonderful post earlier on memoization Stefan. I'm still trying to wrap my head around all the details. For example I'm trying to figure out why (in the second version) the constant "is" scoped within the function isn't garbage collected in between different calls to the function. It seems like there is a lot going on behind the scenes, and even though things look "semantically correct" to a beginner, they aren't so straightforward. :) I think I will re-read your post a couple more time, and hopefully get some more insight. BTW, Sorry I didn't notice your update earlier. For some reason, I only get certain emails from this list, and others disappear down a black hole. I just happened to browse the archives and noticed this response. Is there a web interface or such to browse and/or respond to threads? I just usually mail "beginners(a)haskell.org" which is a painful way to do this... (unless I'm doing it wrong).

1 0

Haskell Bin Tree Cellular Automata.
by Sourabh 06 Jun '15

06 Jun '15

Hello all! I am trying to solve the following problem on HackerRank. It asks us to compute a cellular automata based on a binary tree: https://www.hackerrank.com/challenges/the-tree-of-life I have got 9/10 test cases passing. The last test case times out on the server. But I was able to download the input and expected output, and verify that it is functionally correct. The problem is that the big input is supposed to run within 5 sec, and mine is taking 145 seconds, LOL! Here was my first implementation: https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalP… I figured out that I am constantly re-computing the trees, and decided to try and memoize the results. Here is my memoization attempt: https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalP… Basically I have changed the simulateCellularAutomata function, which computed the new trees, into a list (automataTrees - line 60). I was expecting the results to be memoized, but the runtime is unchanged. I was wondering if someone can help me figure out what I'm doing wrong with the memoization. Or suggest other ways to memoize this perhaps? -- Thanks much! SSJ

5 6

How to use trigonometric functions with Data.Scientific?
by Martin Vlk 03 Jun '15

03 Jun '15

Hi, I am writing a program to do some astronomical calculation, and I am using the Data.Scientific library to represent my floating point numbers. Would anyone know how to use trigonometric functions with the Scientific type? I see: a :: Scientific a = scientific 500036 (-5) sin :: Floating a => a -> a -- this won't work wrongType = sin a Any ideas? Many Thanks Martin

2 2

best way to code this
by briand＠aracnet.com 03 Jun '15

03 Jun '15

Hi, A simple example of something I was trying to do but it had some questions along the lines of "the best way to do this". Given a list l = [a] and an a-list alist = [ (a,b) ] the idea is to find all the items in l which are in alist and then create a list [b] so the overall function should be [a] -> [ (a,b) ] -> [b] the solution is straightforward: l1 = filter (\x -> isJust (lookup x alist)) l l2 = map (\x -> fromJust (lookup x alist)) l1 `fromJust` used in the construction of l2 won't fail, because only the elements for which the lookup succeeded are in l1. This would be something called `filterMap` but I couldn't find such a function in the list library, but it seems like there just has to be one defined in a library somewhere. the above seems clumsy, i'm wondering how to make it "more pretty". generally i was also wondering if the above construction is as inefficient as it looks because of the double-lookup, or would the compiler actually be able to optimize that code into something more efficient ? this code is not being used on large sets of data so efficiency doesn't matter, I'm just curious. Thanks, Brian

4 9

Re: [Haskell-beginners] [Haskell-cafe] I think someone had a complicated program to use brackets for array indexing - is it possible to use a DSL for this?
by Christopher Allen 01 Jun '15

01 Jun '15

Strongly agreed with ok and Tikhon. I've tried these weird pidgins and localized fabrications wrapped around Haskell before, it's only a stumbling block. Haskell is simple, you don't have to lie - just encourage them not to draw false analogies. On Mon, Jun 1, 2015 at 7:52 PM, Tikhon Jelvis <tikhon(a)jelv.is> wrote: > If you teach them about how operators are normal functions in Haskell, > using an operator to index into an array makes the indexing operation less > magical—a big pedagogical boon, in my view. The fewer special cases in the > language you're teaching, the better, and looking similar to other > languages is not a good reason for a special case. > > Especially since the similarity could be misleading!) > > On Mon, Jun 1, 2015 at 5:48 PM, <ok(a)cs.otago.ac.nz> wrote: > >> > I'm a part time tutor even though I don't look Elizabethan >> > >> > I was trying to lower the learning curve for students >> >> Using square brackets for array indexing in Haskell >> would be more a case of putting a stumbling block in >> their way than lowering the learning curve. >> >> Fortran uses A(I), not A[I], and has for the last fifty-some >> years. The official definition of Simula 67 uses A(I) as >> well, despite its predecessor Algol 60 using a[i]. COBOL >> uses A(I), and has done so nearly as long as Fortran. PL/I >> (yes, it still exists) uses A(I), not A[I]. BASIC uses >> A(I), this is still so in Visual Basic.NET. If memory >> serves me correctly, MINITAB uses parentheses, not brackets. >> >> Is a pattern beginning to emerge? >> >> Lying to the students by implicitly telling them "all programming >> languages use square brackets for array indexing" will be doing >> them no favour. Even lying about Haskell is no kindness. >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >> > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > >

1 0

Re: [Haskell-beginners] [Haskell-cafe] I think someone had a complicated program to use brackets for array indexing - is it possible to use a DSL for this?
by KC 01 Jun '15

01 Jun '15

On Jun 1, 2015 5:52 PM, "Tikhon Jelvis" <tikhon(a)jelv.is> wrote: If you teach them about how operators are normal functions in Haskell, using an operator to index into an array makes the indexing operation less magical—a big pedagogical boon, in my view. The fewer special cases in the language you're teaching, the better, and looking similar to other languages is not a good reason for a special case. Especially since the similarity could be misleading!) Good point (s) -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey

1 0

Re: [Haskell-beginners] [Haskell-cafe] I think someone had a complicated program to use brackets for array indexing - is it possible to use a DSL for this?
by KC 01 Jun '15

01 Jun '15

Then a tuple might work better as input to a function to index into an array e.g. myArray (5) -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey On Jun 1, 2015 1:21 PM, "Tikhon Jelvis" <tikhon(a)jelv.is> wrote: > You could make myArray a function that takes a list as an input. Of > course, all your other array functions have to account for this too. A > potential advantage is that this approach leaves the underlying array type > abstract, so you could mix and match different data structure on the > backend. (IntMap, Array, Vector… etc.) > > A disadvantage is that this is non-standard usage which could be confusing > to people and there's no way I know of to statically ensure the list passed > in always had one element. That is, myArray [1, 2] would be legal and > result in a runtime error. > > I don't know of a way to do it while using a normal array type directly. > > On Mon, Jun 1, 2015 at 1:17 PM, KC <kc1956(a)gmail.com> wrote: > >> I think someone had a complicated program to use brackets for array >> indexing - is it possible to use a DSL for this? >> >> That is, to use myArray [5] and have a DSL convert it to standard Haskell >> syntax >> >> -- >> -- >> >> Sent from an expensive device which will be obsolete in a few months! :D >> >> Casey >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >> >> >

2 2

I think someone had a complicated program to use brackets for array indexing - is it possible to use a DSL for this?
by KC 01 Jun '15

01 Jun '15

I think someone had a complicated program to use brackets for array indexing - is it possible to use a DSL for this? That is, to use myArray [5] and have a DSL convert it to standard Haskell syntax -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey

1 0

Command line interface programming
by Dananji Liyanage 01 Jun '15

01 Jun '15

Hi All, I'm in the process of learning Haskell, and I need to write a command line interface program which can interact with the user. Right now, I have a sample program written using 'System.Console.Haskeline' package. Can someone please give me some additional material, which I can read on with respect to this? Thanks in advance! -- Regards, Dananji Liyanage

2 1