Re: [Haskell-cafe] Android and Haskell
On Wed, Jun 17, 2009 at 4:31 PM, Erik de Castro Lopo > wrote: > > Well if the android phones have a JVM then something like OpenQuark > should do the trick. > The Android phones actually have a different VM which essentially takes compiled/translated java bytecode. http://en.wikipedia.org/wiki/Dalvik_virtual_machine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applying Data.Map
Although in this example using Data.Map is overkill, if the alphabet was
very large then Data.Map probably would be the way to go. In that case I'd
use:
map head . group . sort instead of nub . sort
since it's noticeably quicker for large lists. This is because nub needs to
preserve the order of input, removing redundancies, but you're sorting it
anyway.
Also, in map (\c -> m Map.! c) s you can use the 'section' (m
Map.!)instead. e.g., map
(m Map.!) s
The Map.! is ugly though. As you're only using fromList and (!) from
Data.Map, I'd just import those explicitly since they don't clash with
Prelude. Then you'd have map (m !) s
Toby.
On Tue, Jun 9, 2009 at 4:59 AM, michael rice wrote:
> I wrote a Haskell solution for the Prolog problem stated below. I had
> written a function SQUISH before discovering that NUB does the same thing.
> While the solution works, I thought maybe I could apply some functions in
> the Data.Map module, and so wrote a second version of SERIALIZE, one no
> longer needing TRANSLATE. Using the Data.Map module is probably overkill for
> this particular problem, but wanted to familiarize myself with Map type.
> Suggestions welcome. Prolog code also included below for those interested.
>
> Michael
>
> ===
>
> {-
> From "Prolog By Example", Coelho, Cotta, Problem 42, pg. 63
>
>Verbal statement:
>Generate a list of serial numbers for the items of a given list,
>the members of which are to be numbered in alphabetical order.
>
>For example, the list [p,r,o,l,o,g] must generate [4,5,3,2,3,1]
> -}
>
> {-
> Prelude> :l serialize
> [1 of 1] Compiling Main ( serialize.hs, interpreted )
> Ok, modules loaded: Main.
> *Main> serialize "prolog"
> [4,5,3,2,3,1]
> *Main>
> -}
>
> ===Haskell code==
>
> import Data.Char
> import Data.List
> import Data.Map (Map)
> import qualified Data.Map as Map
>
> {-
> translate :: [Char] -> [(Char,Int)] -> [Int]
> translate [] _ = []
> translate (x:xs) m = (fromJust (lookup x m)) : (translate xs m )
> -}
>
> {-
> serialize :: [Char] -> [Int]
> serialize s = let c = nub $ sort s
> n = [1..(length c)]
> in translate s (zip c n)
> -}
>
> serialize :: [Char] -> [Int]
> serialize s = let c = nub $ sort s
> n = [1..(length c)]
> m = Map.fromList $ zip c n
> in map (\c -> m Map.! c) s
>
> Prolog code
>
> serialize(L,R) :- pairlists(L,R,A),arrange(A,T),
> numbered(T,1,N).
> ? <- typo?
> pairlists([X|L],[Y|R],[pair(X,Y)|A]) :- pairlist(L,R,A).
> pairlists([],[],[]).
>
> arrange([X|L],tree(T1,X,T2)) :- partition(L,X,L1,L2),
> arrange(L1,T1),
> arrange(L2,T2).
> arrange([],_).
>
> partition([X|L],X,L1,L2) :- partition(L,X,L1,L2).
> partition([X|L],Y,[X|L1],L2) :- before(X,Y),
> partition(L,Y,L1,L2).
> partition([X|L],Y,L1,[X|L2]) :- before(Y,X),
> partition(L,Y,L1,L2).
> partition([],_,[],[]).
>
> before(pair(X1,Y1),pair(X2,Y2)) :- X1
> numbered(tree(T1,pair(X,N1),T2),N0,N) :- numbered(T1,N0,N1),
> N2 is N1+1,
> numbered(T2,N2,N).
> numbered(void,N,N).
>
> Prolog examples
> Execution:
>
> ?- serialize([p,r,o,l,o,g]).
>[4,5,3,2,3,1]
> ?- serialize ([i,n,t,.,a,r,t,i,f,i,c,i,a,l]).
> [5,7,9,1,2,8,9,5,4,5,3,5,2,6]
>
>
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginners question about fromMaybe
> where next = probePhase ... > key = ... > Argh, I really wish Gmail would allow me to compose in a fixed with width font! Does anyone know of a setting or something that I'm missing? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginners question about fromMaybe
On Wed, Jun 3, 2009 at 8:59 AM, Nico Rolle wrote: > hi there > > heres a code snipped, don't care about the parameters. > the thing is i make a lookup on my map "m" and then branch on that return > value > > probePhase is sc [] m = [] > probePhase is sc (x:xs) m > | val == Nothing = probePhase is sc xs m > | otherwise = jr ++ probePhase is sc xs m > where > jr = joinTuples sc x (fromMaybe [] val) > key = getPartialTuple is x > val = Map.lookup key m > > > the line "jr = joinTuples sc x (fromMaybe [] val)" is kind of ugly > because i know that it is not Nothing. Although pattern matching is probably nicer, there's also fromJust which will throw an exception if you pass it Nothing. I prefer: case Map.lookup key m of Nothing -> next Just val -> (joinTuples sc x val) ++ next where next = probePhase ... key = ... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Best text editor
On Wed, Apr 15, 2009 at 8:57 AM, Jeff Wheeler wrote: > > As one of the Yi developers, I'd love to hear some more specific > feedback on this. Do you remember any specific Vim features that were > missing? My main gripe with the vi emulation in Yi was in vty mode[1] and how it was unable to tell that 'esc' wasn't always 'meta-'. e.g., If I leave insert mode with esc and hit j to go down a line too quickly it interpreted it as meta-j. Quite annoying. This was a little while ago though. Also, I remember the cursor would go beyond the last character in a line in command mode, which is very un-vi-ish. At the time I remember thinking I should try and fix these things myself... but.. umm... [1] vty Yi is the only one I would use--coding must always live inside a screen session :) I really dislike wrapping a GUI around vi(m). I don't want toolbars, tabs, scrollbars nor menus. I don't even want a titlebar. Absolute full screen terminal running screen is perfect. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Retargeting the ghc code generator
2009/4/3 Vasili I. Galchin : > Hello, > > Is there any project to retarget the GHC code generator to generate > Common Intermediate Language(CLI) in order to run on Mono or .NET? I assume > that Mondrian did precisely that. There are/were a couple of projects attempting that or to bring Haskell to .NET in general, but with limited success. MSR were considering it but due to qualities like purity and laziness making it difficult they chose to bring Ocaml to .NET and came up with F#. http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Translating an imperative algorithm - negascout
On Fri, Feb 27, 2009 at 7:54 AM, Colin Paul Adams
wrote:
> Hello Haskellers,
>
> I want to implement the negascout algorithm for the game I'm writing.
>
> Wikipedia gives the algorithm in imperative terms:
>
> http://en.wikipedia.org/wiki/Negascout
>
> I've tried to translate this into Haskell. I'm not sure if I'm going
> about it the right way, and if I am, if I've done it correctly.
In my opinion keeping the code looking vaguely like the pseudo-code is
a good idea for when you revisit it weeks later and try to remember
what the hell you were originally doing.
But I don't want to try and refactor the code you've provided without
some tests to ensure everything is correct. Rule number one for
refactoring. :) But for starters I imagine it's far more readable to
covert all the 'case boolExpr of' expressions to 'if then else'.
Secondly there's a lot of repeated functionality in there that should
be abstracted to smaller functions, which I think could still be done
without sacrificing the correlation to the algorithm pseudocode.
There's 3 parts which check if alpha is greater than beta which could
be abstracted and there's the check if rest is empty else recurse
which could be abstracted. negascout' would be far more readable if
you did this as long as you gave the helper functions good names. :)
Sorry to be so vague though. If you have some data and tests then I
can help you out some more if you like.
> Any comments on my effort here, are welcome:
>
> module Move (negascout
> ) where
>
> {-# contract negascout Ok -> {depth | depth >= 0} ->
> Ok -> Ok -> Ok #-}
> negascout :: Node -> Int -> Int -> Int -> Int
> negascout node depth alpha beta =
> case depth == 0 || is_terminal node of
> True -> evaluate node
> False -> let child:rest = children node
> b = beta -- initial window is (-beta, -alpha)
> in negascout' child (depth-1) (- b) (- alpha) beta rest
>
>
> -- Implementation
>
> {-# contract negascout' Ok -> {depth | depth >= 0} ->
> Ok -> Ok -> Ok -> Ok -> Ok #-}
> negascout' :: Node -> Int -> Int -> Int -> Int -> [Node] -> Int
> negascout' node depth beta' alpha beta rest =
> let a = negate $ negascout child depth beta' alpha
> in case a > (- alpha) of
> True -> let alpha' = a
> in case alpha' >= beta of
> True -> alpha' -- beta cut-off
> False -> case alpha' >= (- beta') of -- null window
> failed high?
> True -> let alpha'' = negate $ negascout
> child depth (- beta) (- alpha') -- full re-search
> in case alpha'' >= beta of
> True -> alpha'' --
> beta cut-off
> False -> case rest of
> [] ->
> alpha''
>
> child':rest' -> let b' = alpha'' + 1
>
> in negascout' child' depth (- b') alpha'' beta rest'
> False -> case rest of
> [] -> alpha'
> child':rest' ->
> let b' = alpha' + 1
>
> in negascout' child' depth (- b') alpha' beta rest'
> False -> case rest of
> [] -> alpha
> child':rest' -> let b' = alpha + 1
> in negascout' child'
> depth (- b') alpha beta rest'
>
>
> --
> Colin Adams
> Preston Lancashire
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Looking for pointfree version
On Thu, Feb 12, 2009 at 6:46 PM, Kim-Ee Yeoh wrote: > > On the same note, does anyone have ideas for the following snippet? Tried the > pointfree package but the output was useless. > > pointwise op (x0,y0) (x1,y1) = (x0 `op` x1, y0 `op` y1) $ pointfree '(\op (a, b) (c, d) -> (a `op` c, b `op` d))' (`ap` snd) . (. fst) . flip flip snd . ((flip . (ap .)) .) . flip flip fst . ((flip . ((.) .)) .) . (flip =<< (((.) . flip . (((.) . (,)) .)) .)) 'Useless' is a bit understated , IMO. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re[4]: [Haskell] Google Summer of Code
On Thu, Feb 12, 2009 at 8:11 AM, Bulat Ziganshin wrote: > Wednesday, February 11, 2009, 11:55:47 PM, you wrote: > >> And ghc is still making large improvements with >> each release, whereas gcc isn't likely to get significantly better. > > yes, it's close to perfect LOL! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Employment
On Fri, Jan 23, 2009 at 11:56 AM, Jonathan Cast wrote: > > Not really. My company *advertises* for Haskell developers, and then > when they come in to interview, informs them that the code base is > actually written in Perl. Works, too --- we have several Haskellers > working here. If all you care about is the quality of the developers, > and not their productivity once you've got them, you don't actually need > to let them use Haskell after the interview is over... I saw this trick recently for a job advertised locally to me, in Melbourne. I was initially pretty excited that someone in this city was actually advertising for Haskell programmers, until I realised they needed to be good at Javascript and Perl so they could work on their web apps. Argh, I didn't bother applying. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Parsec question
On Wed, Dec 24, 2008 at 9:22 AM, Erik de Castro Lopo
wrote:
>
> My next problem is matching things like:
>
> identifier ('.' identifier)* ('.' '*')?
>
> I've had a look at lookAhead from Text.ParserCombinators.Parsec.Combinator
> but I can't get it to work.
* is analogous to the 'many' combinator, and ? can be implemented with
the 'option' combinator. Parsec is all about composing bigger parsers
out of smaller ones using combinators like these.
One of the tricks I found early on is to understand where to use 'try'
(since by default input is consumed even if a parser fails) but apart
from that just read Daan's page, even though it's out of date, and
look at how all these cool combinators work.
http://legacy.cs.uu.nl/daan/download/parsec/parsec.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Fun with type functions
On Thu, Nov 27, 2008 at 8:29 PM, Simon Peyton-Jones <[EMAIL PROTECTED]> wrote: > So this message is to ask you: > >can you tell us about the most persuasive, fun application >you've encountered, for type families or functional dependencies? I only just discovered functional dependencies a week or two ago, and when it solved my problem it absolutely made my day. I was reading 'Bananas, Lenses, etc.' and wanted to implement paramorphic recursion with a type class. My initial attempt: class Paramorphic p where term :: p -> Bool this :: p -> a next ::: p -> p para :: (Paramorphic p) => t -> (a -> (p, t) -> t) ->p -> t para a f p | term p = a | otherwise = f (this p) (next p, para a f (next p)) instance Paramorphic Int where term = (== 0) this = id next = subtract 1 This is broken, since 'a' in 'this' is loose. Then I found multiple class parameters: class Paramorphic p a where ... But 'a' was still too loose--para's type became para :: (Paramorphic p a, Paramorphic p a1, Paramorphic p a2, Paramorphic p a3) => t -> (a1 -> (p, t) -> t) -> p -> t But a fundep solved it for me: class Paramorphic p a | p -> a where ... I could now pretty much do factorial and tails from the paper. fact = para 1 (\a (_, b) -> a * b) instance Paramorphic [a] a where term = null this = head next = tail tails = para [[]] (\a (as, b) -> (a : as) : b) Not exactly a 'fun' example, but I was smiling for hours after discovering this. :) Toby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List as input
On Thu, Oct 16, 2008 at 9:01 AM, Dan Weston <[EMAIL PROTECTED]> wrote: > Google "median order statistic". > > E.g. this is an interesting (and colorful) discussion: > > http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/60D030CD-081D-4192-9FB5-C220116E280D/0/lec6.pdf Hrmm, maths and statistics definitely aren't a strong area for me, but doesn't that PDF say on the second page that choosing i = 0 or i = n or i = median is equally naive? The rest of the document describes other interesting methods for getting the pivot. I couldn't follow the Wikipedia page on order statistics though. Still, with no assumptions as to the contents of a list whatsoever, when choosing 1 element to be the pivot, intuitively it makes no difference which one you choose. (Then again, I find statistical analysis rarely is intuitive.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List as input
On Wed, Oct 15, 2008 at 5:44 PM, leledumbo <[EMAIL PROTECTED]> wrote: > > module Main where > > import Data.List > > -- quicksort of any list > qsort [] = [] > qsort (x:xs) = qsort(filter(=x) xs) > > -- optimized quicksort, uses middle element as pivot > qsortOpt [] = [] > qsortOpt x = qsortOpt less ++ [pivot] ++ qsortOpt greater > where >pivot = x !! ((length x) `div` 2) >less = filter (greater = filter (>=pivot) (delete pivot x) > > main = do > putStr "Enter a list: " > l <- readLn > print (qsortOpt l) > -- end of code I'm curious as to why taking the pivot from the middle is an 'optimized' version. For this to be true you must be making some assumptions about the contents of the list. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie seeking advice regarding data structure for a tricky algorithm
Hi, I'm trying to implement a fast kd-tree in Haskell. http://en.wikipedia.org/wiki/Kd-tree It's a binary tree representing space partitions. One of the fastest ways to build kd-trees is outlined in this paper: http://www.cgg.cvut.cz/~havran/ARTICLES/ingo06rtKdtree.pdf (I'm trying to implement Algorithm 5 on page 5 and the steps outlined in section 4.3.1.) I'll try to outline a simplified analogous algorithm to demonstrate my problem. It's all about classifying which children should go in a left or right branch using heuristics. Say I want to put the words 'foo', 'bar' and 'baz' into a binary tree. The heuristic requires I split the words into letters and sort them: 'aabbfoorz'. The heuristic then may decide, based on the sorted letters, that 'bar' and 'foo' should go in the left child and 'baz' goes in the right. Typically we'd then simply recurse and for example, the left child's words would be re-sorted into 'abfoor' and the heuristic is reapplied. If we assume that sorting is relatively expensive, we can avoid the re-sort for the children by unmerging the parent's sorted list of letters. Two sublists of a sorted list should already be sorted. If we know which word each letter belongs to it would be more efficient to tag the letters with 'left' or 'right' as the words are classified. Then we can iterate down the sorted letter list and produce new sorted sublists rather simply. So it's not actually that complicated, and I can imagine exactly how it could be done in C but I really don't know how to approach this in Haskell. The problem I'm having is how to keep a map between the words and its letters (which in the real problem is a map between a list of vectors and 6 tuples containing Doubles and enumerations) while keeping in mind you can't just map any letter to a word, but specific letters. e.g., the 'b's in the example must remember specifically whether they belong to 'bar' or 'baz'. Thanks for any insights, Toby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Origins of (x:xs)?
Hi, This may have been asked before, sorry if so. I've wondered where the convention of pattern matching a list to (x:xs) came from? I've read a couple of old papers recently which let me believe it may have started back in the '70s with Miranda and its ilk. Does anyone know why (x:xs)? Is xs meant to be a synonym for 'excess'? Yours curiously, Toby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: practice problems?
On 9/5/06, Tomasz Zielonka <[EMAIL PROTECTED]> wrote: On Mon, Sep 04, 2006 at 07:39:40PM +0200, [EMAIL PROTECTED] wrote:> The ultimate Haskell challenge is of course the ICFP contest> http://icfpcontest.org/> There is also the International ACM Programming Contest>http://acm.uva.es/problemset/I don't know about the services mentioned above, but Sphere Online Judge (http://www.spoj.pl/) allows you to submit solutions written in Haskell(and many other programming languages).As a Haskell newbie I've found the SPOJ challenges challenging, usually due to the time contraints placed on solutions. Another 'challenge site' I've enjoyed tremendously is Project Euler at http://mathschallenge.net/index.php?section=projectToby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: "class []" proposal Re: [Haskell-cafe] One thought: Num to 0as ? to list?
On 8/23/06, Donald Bruce Stewart <[EMAIL PROTECTED]> wrote: I use the following script from vim to infer top level type declarationsfor me. I've found it particularly useful for understanding others' code:On the topic of coding Haskell with Vim is there an indentation plugin for Haskell available? Google hasn't found one for me and none ismentioned on the Haskell wiki.Thanks,Toby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
