April 2010 - Haskell-Cafe

US Patent for the idea of using Haskell to implement UAX #9
by Brian Hulley 19 Apr '10

19 Apr '10

Hi everyone, It's been a long time since I last posted to this list since I'm currently working on something that is not directly Haskell-related, but it still relates to functional programming in general. Anyway imagine my surprise when an innocent search for some keywords (I can't remember the exact ones but the following gives similar results) haskell unicode bidirectional revealed a link to a US Patent (7120900) for the idea of implementing the Unicode Bidirectional Algorithm (UAX #9 http://www.unicode.org/reports/tr9) in Haskell, making use, as far as I can tell, of nothing more than the normal approach any functional programmer would use, namely separation of concerns etc. The link is http://www.freepatentsonline.com/7120900.html though I think it would be better if they had just called the website "free handcuffs online" because that is what it amounts to when people succeed in preventing others from using ideas, especially ideas everyone would easily think up by themselves. Before going further I would like to explicitly state that I would not wish to cast any aspersions upon the people or companies involved in this patent, since it is all too clear to me that these people have acted in a perfectly legal way and are just doing their various jobs: in other words it's an "I'm a lumberjack and I'm ok..." kind of scenario: everyone probably thinks of themsevles as being a perfectly nice upstanding person, and if I met any of them face to face I'm sure I would find that they are *indeed* really nice friendly people who believe that they are doing absolutely the right and logical thing. In fact many nice people I myself have talked to about my own ideas immediately suggest that I should "obviously" patent them: it takes a long time to explain to them why this would not actually further my goals at all, and it is difficult for them to understand my explanation because the problem is rather too subtle for people who have not already been thinking along these lines for a while. However all this does not affect the problem that this patent acts as a brick in the general structural evil in our world today: anyone who is trying to create a programming language environment that is accessible to people who use right-to-left languages is now between a rock and a hard place when it comes to implementing UAX #9, the standard Unicode algorithm for implementing the Unicode semantics of bidirectional text. In this particular case, I expect (but I'm not a lawyer so please don't take this as solid advice: it's just a hope) that a workaround for Haskell programmers would be to discard their natural desire to use a functional approach and instead just implement UAX #9 verbatim using the ST monad. (The patent also tries to extend itself to other functional languages so caution is needed all round.) But although the above workaround *might* be legal in this particular instance it seems to me that as programmers we must not just let our craft be dominated by the psychopathic tendencies of certain elements in society that work hard to try to squash the ``normals'' into a life of brutal misery while they rampage ruthlessly about with a biological inability to experience empathy for other human beings. (www.ponerology.com) The memetic virus of psychopathy is rapidly spreading throughout human civilization and most people are not conscious enough of the elements that are contributing towards their own behaviour, thus ignoring the fact that the rice they eat for supper might have been picked by a tiny little girl in China with bleeding fingers or the carpet they walk on may have been made by a little 8 year old boy slave chained all day to a loom in a shed in India. To this end I humbly appeal to everyone here to please help in the fight against software patents, so that we can begin the huge task of reclaiming our world for real people who understand that true meaning in life comes from extending our feeling of self into the world beyond our own body: http://petition.stopsoftwarepatents.eu/ http://ffii.org Thanks a lot for reading this, Brian. [expecting to be crucified, but if it helps just one little girl or boy it will be worth it!] Disclaimer: this email is entirely my responsibility and I am not acting on behalf of any of the above web sites.

10 14

Re: [Haskell-cafe] hamming distance allocation
by John Lato 19 Apr '10

19 Apr '10

> Subject: Re: [Haskell-cafe] hamming distance allocation > > Am Montag 19 April 2010 01:03:14 schrieb Arnoldo Muller: >> Hello all: >> >> I want to generate some hamming distance statistics about a set of >> strings. As explained in another e-mail in this list, I used the >> following code to call the >> functions: >> (exampl holds the list of strings of size w) >> filter (\x -> x /= 0) $ map (uncurry hammingX) [(xs, ys) | xs <- exampl, >> ys <- exampl] >> >> I have two hamming functions: >> -- hamming distance for variable length strings >> hamming :: String -> String -> Int >> hamming x y = hamming' x y 0 >> where >> hamming' [] _ !c = c >> hamming' _ [] !c = c >> hamming' (x:xs) (y:ys) !c >> | x == y = hamming' xs ys c >> | otherwise = hamming' xs ys (c + 1) >> >> -- function posted in this mailing list >> hamming2 :: String -> String -> Int >> hamming2 xs ys = length (filter not (zipWith (==) xs ys)) >> >> I am executing these functions millions of times and the bottleneck of >> my program is in them as explained by running in profiling mode with >> +RTS -K400M -p -RTS >> >> The costlier function is the hamming distance >> COST CENTRE MODULE %time %alloc >> >> hamming Distances 66.6 41.9 >> >> It says that it is performing 41% of the allocations. In the case of >> hamming2 the allocations go as far as 52%. > > Allocations are cheap, so that's not necessarily a problem. More important > is, what's the maximum residency and how much is copied during GC? > Are you compiling with -O2 ? > >> I could understand that >> there are allocations in "hamming2" because we are creating pairs, but >> in the case of "hamming" there should be no allocation. > > Why not? I don't know how GHC counts allocations, but everytime you go from > (x:xs) to xs, you need a new pointer to the tail. If that counts as > allocation, hamming must allocate a lot, too. Is it really necessary to use Strings? I think a packed type, e.g. Vector or ByteString, would be much more efficient here. Of course this is only likely to be a benefit if you can move away from String entirely. I suspect that "hamming2" would perform better then. John

3 4

help with Haskell programming
by Mujtaba Boori 19 Apr '10

19 Apr '10

Hello I am kinda newbie in Haskell you can help help me with some programming I am trying to make function like for example func :: (a -> Bool) -> (a -> Bool) this function make calculation and return bool . I want to be able to make bool True when It is False and False when it is True while returning the a. Thank you -- Mujtaba Ali Alboori

5 8

Patch to add process group support
by Hamish Mackenzie 19 Apr '10

19 Apr '10

The attached patch for the process package adds support for creating and interrupting process groups on Unix and Win32 systems. Currently we have to use a nasty hack in Leksah that only works on Unix systems (and even then not very well). On Win32 Leksah's background build feature is dreadful as a results (because it has no way to interrupt the build and start over when the user makes more changes). I would love to get this onto Hackage somehow, if not as a new version of the process package, perhaps as an alternative package ("process-groups" using System.Process.Groups instead of System.Process). Please can you have a look and let me know what you think? Thanks, Hamish This patch introduces the following functions to System.Process * runCommandNewGroup, runProcessNewGroup, runInteractiveCommandNewGroup and runInteractiveProcessNewGroup __ These are variations on the existing functions for running processes. They create the child process as the lead process in a new process group. Unix - calls setpgid in both the parent and the child process after fork. Win32 - calls CreateProcess with the CREATE_NEW_PROCESS_GROUP set. I also had it unset CREATE_NO_WINDOW because this seems to prevent the child attaching to the parents console (and therefor stops interuptProcessGroup from working). * interruptProcessGroup This function can be used interrupt a running process group. Unix - calls signalProcessGroup to send sigINT Win32 - If the process ID is known it calls generateConsoleCtrlEvent to send cTRL_BREAK_EVENT __ Compatibility __ Backward Compatibility CreateProcess has a new field new_group which may need to be added to some existing code. If set to False the current behaviour is preserved. As far as I know this is the only change that could break existing code. Linker Errors I have renamed the C functions it used in order to prevent linker errors when using this new version with the existing process package. __ Win32 Only __ On Win32 the process handle is not the same as the process ID and there is no reliable way to convert from one to the other. I have added an interface that allows access to the process ID, but does not change the behaviour of the existing functions. * PINFO Replaces PHANDLE in the ProcessHandle type. type PINFO = (PHANDLE, Maybe Word32) -- Handle and Process ID * mkProcessHandleWithPID Like mkProcessHandle but allows you to specify the processes ID as well. This function is now used in all the run functions so the ProcessHandle they return will contain a process ID. * withProcessInfo and withProcessInfo_ Like withProcessHandle functions but gives you access to the PINFO (not just the PHANDLE it contains).

2 2

Re: [Haskell-cafe] hamming distance allocation
by John Lato 19 Apr '10

19 Apr '10

> From: Daniel Fischer <daniel.is.fischer(a)web.de> > > Am Montag 19 April 2010 14:37:33 schrieb John Lato: >> Is it really necessary to use Strings? I think a packed type, e.g. >> Vector or ByteString, would be much more efficient here. > > Not very much if the strings are fairly short (and the list isn't too long, > so there's not a big difference in cache-friendliness). > If eight-bit characters aren't enough, packing the strings into > UArray Int Char gives performance quite close to ByteStrings. I agree, provided that the Strings are used only once. I missed the first part of this thread, so there may be context I don't have, but if Strings are retained and the Hamming distance calculated for multiple pairings, I think it would be a noticeable difference. Although probably not as much as reducing the number of calls to Hamming as you and H. Apfelmus suggest. John

1 0

Functional Dependencies conflicts
by Limestraël 19 Apr '10

19 Apr '10

Hello, I'm trying to make two simple classe which would help me to transform unserializable datatypes to serializable ones. The classes are: class (Binary b) => Binarizable a b | a -> b where toBinary :: a -> b class (Binarizable a b, Monad m) => Unbinarizable a b m | a -> b where fromBinary :: b -> m a The idea is simple: if we have a type 'a' which cannot be serialized (for instance because it contains functions), we may turn it into a 'b' type which is instance of Binary, with of course a loss of information. And then, Unbinarizable enables us to get the original 'a' type back. fromBinary has to run inside a monad so that it can somehow recover the lost information. Now, for instance, in a simple role playing game, we would have the datatype : data GameObject = GameObject { objIdentifier :: String, objEffect :: Character -> Character } It can't obviously be declared instance of Binary, since the field objEffect is a function. So -- since an objIdentifier must be unique -- we can declare it instance of Binarizable/Unbinarizable: instance Binarizable GameObject String where toBinary = objIdentifier instance (MonadReader [GameObject] m) => Unbinarizable GameObject String m where fromBinary name = liftM getIt ask where getIt = maybe err id . find ((== name) . objIdentifier) err = error $ "Unbinarize: The object '" ++ name ++ "' doesn't exist!" To be unbinarized, we need to have a ReaderMonad which grants us access to the list of all the objects, so that we may find the object from its identifier. Well, here comes the trouble: GameStructs.hs:16:9: Functional dependencies conflict between instance declarations: instance (Binary a) => Binarizable a a -- Defined at MagBots/GameStructs.hs:16:9-37 instance Binarizable GameObject String -- Defined at MagBots/GameStructs.hs:38:9-37 GameStructs.hs:19:9: Functional dependencies conflict between instance declarations: instance (Binary a, Monad m) => Unbinarizable a a m -- Defined at MagBots/GameStructs.hs:19:9-50 instance (MonadReader [GameObject] m) => Unbinarizable GameObject String m -- Defined at MagBots/GameStructs.hs:41:9-73 I don't see why the functional dependencies conflict, since GameObject is not an instance of Binary...

6 13

Embedded funcional programming?
by Maurício CA 18 Apr '10

18 Apr '10

Hi, all, I've beeing working with some people who do programming for wireless devices. 100% of their code uses C, and I would like to show them nice things they could do with funcional programming (not necessarily Haskell. I believe, say, Standard ML could be also very nice.) I'm new to this, so the only problems I see are finding a compiler that targets the platform (ARM7, for instance, or others) and uploading the compiled firmware to the device. Do you think this can be a straightforward path? Thanks, Maurício

9 8

Re: Ocaml for Haskellers tutorial
by Pierre-Etienne Meunier 18 Apr '10

18 Apr '10

Hi, Strangely enough, I did the opposit some time ago. Ocaml is way simpler than haskell, in fact. There is no referential transparency, no laziness (though it can be simulated with "fun ()->x", but the type of a lazy expression is not the same as the reduced expressions), no parallelism (the GC is not parallel). There are no list comprehensions. The syntax for pattern matching is simpler but more restrictive, and there are loops. There are also objects, but even good caml programmers (i.e. at ICFP level) do not use it. Also, there are fewer available libraries, due to a quite immature FFI. I should also say that the top-level is of much greater help than ghci, and I strongly recommend using tuareg-mode with emacs, which make up a very powerful combination. Have a look at these examples : let fact n= if n=0 then 1 else n*(fact (n-1)) This function is of type Int->Int because the arithmetic operations are monomorphic (there are no typeclasses). If you wanted to do it with Doubles, you would have used *. +. and -. For other types, you would have been on your own ;-) let quickSort l=match l with []->[] | h::t -> let (a,b)=List.partition (fun x->x<=h) t in List.append (quickSort a) (h::(quickSort b)) As you can see, match is pretty close to case, except that it requires | between clauses, because the indentation is not significative. Also, lambda abstractions are called fun x-> instead of \x->. There is a syntactic sugar for combining lambdas and match : function []->M | h::t->M' which translates as fun x->match x with ... You cannot see it here, but camlists do not define variables with indentations as in : let a= b= in This would be "let a=... in let b=... in" with any number of lines and arbitrary indentation. Or "let a=... and b=... in", for instance if you want mutually recursive functions. This is because an ocaml file is evaluated in the order in which it is written, which allows for a cool top-level (by the way, the cool emacs command is C-x-e, "evaluate last expression" in tuareg mode). The module system seems sometimes obscure, as modules do not correspond always to files, and you can define several modules in a file. You can read http://caml.inria.fr/pub/docs/manual-ocaml/manual004.html to get an idea. You can define custom types. There is not newtype in haskell, and the keywords for type and data are the same : type tree a = Leaf of a | Node of (tree a)*(tree a) Then you can match on it : match t with Leaf x-> Node (x,y)-> How to do monads ? It is very simple, actually. Some expressions are of type (), with great similarity to IO (). >>= is expressed like in C, with ; print_string "This is a string"; print_int (a+b); a Would translate in haskell as : do putStr "This is a string" print $ a+b return a But the typesystem of ocaml does not require you to use monads. Also, you may have notice that there is no $ in ocaml. There is also a very fine exception system : exception MyException; exception MyException'; try if a=0 then raise MyException else raise MyException' with MyException -> print_string "MyException" | MyException' -> print_string "MyException'" Which allows you to match the value of what error you program did. The last thing you can use is references and loops : for i=0 to n do ... done; let a=ref 10 while (!a)=0 do print_int (!a); a := (!a)-1 done; Most of the time you use mapM_ in haskell, you can do it with loops and references in ocaml, and you save the memory allocation of the list (which is not a lot, I know). You can also notice that references are much simpler to use than in haskell, due to "implicit monads" and unsafePerformIO everywhere. What else ? Records and record updates (you may find this in the manual). And objects : maybe your future boss smokes objects, thus you can learn about this in the manual. A good point in ocaml is that the program does, to a large extent, exactly what you write, in the order you write it.Thus, it is often simpler to know where exceptions occur, and performance is less an issue than in haskell. In fact, haskell waited more than ten years before producing fast code, whereas ocaml did it almost from the beginning. Good luck ! Pierre-Etienne

2 3

Re: Move MonadIO to base
by David Menendez 18 Apr '10

18 Apr '10

On Sun, Apr 18, 2010 at 5:02 PM, wren ng thornton <wren(a)community.haskell.org> wrote: > Heinrich Apfelmus wrote: >> >> Anders Kaseorg wrote: >>> >>> This concept can also be generalized to monad transformers: >>> >>> class MonadTrans t => MonadTransMorph t where >>> morph :: Monad m => (forall b. (t m a -> m b) -> m b) -> t m a >> >> [...] >> However, not all control operators can be lifted this way. Essentially, >> while you may "downgrade" an arbitrary selection of t m a values you >> may only promote one m a in return and all have to share the same >> return type a . In particular, it's not possible to implement >> >> lift :: (Monad m, MonadTrans t) => m a -> t m a > > Why not? > * morph says m(t m a) is a subset of (t m a) > * Monad m says we can fmap :: (a->b) -> (m a->m b) > * Monad (t m) says we can return :: a -> t m a > > lift ma = morph (\k -> k (fmap return ma)) Maybe something like this? lift m = morph (\k -> m >>= k . return) -- n.b., return and >>= are from different monads > Again, having m(t m a)->(t m a) is strictly more expressive than only having > (m a)->(t m a) because the former may avail itself of operations/operators > of t. join . lift :: m (t m a) -> t m a morph is more powerful than lift, but it isn't because of the type. -- Dave Menendez <dave(a)zednenem.com> <http://www.eyrie.org/~zednenem/>

1 0

vector recycling
by Ben 18 Apr '10

18 Apr '10

hello -- this is mostly a question for roman, or don, i guess. suppose i have a list of similarly-sized vectors, and i want to add them up (possibly with coefficients), to yield a result vector. something like module Main where import qualified Data.Vector.Generic as V import qualified Data.Vector.Unboxed as UV type Vec = UV.Vector Double axpy :: Double -> Vec -> Vec -> Vec axpy a x y = V.zipWith (+) (V.map (* a) x) y sumVecs :: [(Double, Vec)] -> Vec sumVecs axs = let (a, x) = head axs in foldl adder (V.map (* a) x) (tail axs) where adder :: Vec -> (Double, Vec) -> Vec adder v1 (a, x) = axpy a x v1 how to i write this in a way which ensures recycling / fusion, e.g. in-place updates? best regards, ben

3 4