July 2004 - Haskell-Cafe

Data.Set subset function?
by Graham Klyne 22 Jul '04

22 Jul '04

I don't see a subset function in Data.Set. What is the preferred way to define this? I currently have: a `subset` b = isEmptySet (a `minusSet` b) (Hmmm... does library style prefer `subset`, `subsetOf`, `isSubset`, `isSubsetOf` ?) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

RE: [Haskell-cafe] STG optimization
by Simon Marlow 21 Jul '04

21 Jul '04

On 20 July 2004 22:58, 7253146(a)informatica.alumnos.uma.es wrote: > So far so good. Nonetheless, some doubts have arisen when I have > started to try to add updating. In the paper, implementation for > "update in place" is extensively discussed, although it is said it > could greatly increase the memory space usage. ¿Has this risk been > measured? I think deforestation can minimize the risk; however, as > far as I know, deforestation is only applied to lists. Nowadays GHC doesn't do update-in-place. We removed update-in-place when we re-implemented the code generator and RTS back in version 4.00. There were two reasons: - update-in-place (and its friend, return-in-registers) turned out to be hugely complex when combined with all the other optimisations that GHC does. - we achieve much of the same benefit by adding unboxed tuples to the language and using the "Constructed Product Result" optimisation. CPR is now done by the strictness analyser. Nevertheless, for a while we still did update-in-place when the code genreator could statically determine that there was an update frame on the top of the stack when building a constructor application. But this could only be done when the constructor application contained no pointers - because otherwise the update-in-place code has to deal with the complexities of mutation in a generational garbage collector. But when combined with concurrency, even this kind of update-in-place is difficult, because it might be that another thread is waiting on the result of the thunk being evaluated, and the update code has to wake up that thread. So now, all updates go through one carefully optimised piece of code in the runtime. > But the STG paper ignores an optimization readyly available to me: > whenever a constructor is allocated (constructor's register > allocation aside, since the push/enter - eval/apply paper says GHC no > longer supports it), the STG machine (the one described by the paper) > takes heap space for it, although an update (indirection or copying) > is going to be done most of times. This leads to potentially bad heap > space usage and more garbage collections. > > I think update frames may be detected by the constructor allocation > code, so it could determine whether to allocate a new constructor or > build it over the closure to be updated. This could be achieved by > marking continuations and update frames in the stack, so constructor > allocation code could distinguish between them. This is inconvenient > because common continuations should remove the mark too, so I do not > like it. Yes you could do this. Don't forget to take into account the complications I mentioned above, though (much easier if you don't have generational collection and concurrency). Also you have to know whether the thunk is big enough to be updated with the constructor application. Cheers, Simon

1 0

Sets and Monads and comprehensions
by Graham Klyne 21 Jul '04

21 Jul '04

A few months ago, there was a discussion here about defining Set to be a Monad, starting with: [1] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005988.html in response to which, SPJ pointed out that a Set cannot be a Monad: [2] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005995.html I found myself treading a path which led me to asking the same question as [1]. Given the answer [2], I'd like to stand back a little and ask if there's another way to tackle my niggle: what I'm interested in is a set comprehension expression that is analogous to a list comprehension expression; e.g. in: [[ > import Data.Set > > type AtomicConcept = String -- named atomic concept > type AtomicRole = String -- named atomic role > > type AtomicConcepts a :: AtomicConcept -> (Set a) > type AtomicRoles a :: AtomicRole -> (Set (a,a)) > > type Interpretation a :: (Set a,AtomicConcepts a,AtomicRoles a) ... > iAL (idom,ic,ir) (ALAll r c) = mkSet [ a | (a,b) <- setToList (ir r) > , b `elementOf` ir c ] ]] is there a common or similar idiom to achieve the same effect without converting the set to a list and back? I did also find myself wondering if there was a role for unfold (or similar) here. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

STG optimization
by 7253146＠informatica.alumnos.uma.es 20 Jul '04

20 Jul '04

Hi. I have been reading recently the STG machine paper by Simon Peyton-Jones. It is relatively easy to follow the explanation, though the formal description of operational semantics is hard to understand. In order to fully understand it, I have started to implement a C-based mini STG machine, implementing the obvious compilation schemes according to the STG paper. Of course, I have not implemented most of optimizations: environment management is very rudimentary, it has three stacks (pointer args, primitive args and continuations) for simplicity, etc. At the moment I have a beatiful tree-reduction STG machine. So far so good. Nonetheless, some doubts have arisen when I have started to try to add updating. In the paper, implementation for "update in place" is extensively discussed, although it is said it could greatly increase the memory space usage. ¿Has this risk been measured? I think deforestation can minimize the risk; however, as far as I know, deforestation is only applied to lists. But the STG paper ignores an optimization readyly available to me: whenever a constructor is allocated (constructor's register allocation aside, since the push/enter - eval/apply paper says GHC no longer supports it), the STG machine (the one described by the paper) takes heap space for it, although an update (indirection or copying) is going to be done most of times. This leads to potentially bad heap space usage and more garbage collections. I think update frames may be detected by the constructor allocation code, so it could determine whether to allocate a new constructor or build it over the closure to be updated. This could be achieved by marking continuations and update frames in the stack, so constructor allocation code could distinguish between them. This is inconvenient because common continuations should remove the mark too, so I do not like it. Another (my favourite) similar solution should be introduce a new stack only for update frames, but still pushing code labels for updating in the continuation stack (which could still be merged with the primitive args stack): this way, constructor's code can still simply jump to the next "continuation" (the update code should be responsible of popping the update stack), and constructor allocation code can simply test if the "continuation" on top of the stack is a real continuation, so it can safely take newly allocated heap space for the constructor, or it is an update (perhaps by testing for equality with the top of the update stack), so the code should test if the constructor closure can be overwritten over the closure to be updated. To ilustrate my thoughts: \begin{code} some_func <some_args> = let b = <some_expression> in SomeConstructor { b, some_stuff } some_other_func <some_other_args> = let a = some_func { some_other_stuff } in case a of <some_alternatives> \end{code} In the above piece of core STG language, when the "a" closure is entered and finally "SomeConstructor" must be allocated, the code of "some_func" should check if the continuation leads to an update (in this case, an update of "a") or an continuation. In this case it leads to an update, so then the code should check if the update closure ("a") is large enough, and, in that case, build the constructor closure over it. Maybe this technique is irrelevant for performance, too expensive to implement, or having a separated update stack is too inconvenient, or these effects are achieved by other ways? Thanks in advance Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

2 1

Re: [Haskell-cafe] How do I include polymorphic function type signatures in a data element ?
by Crypt Master 20 Jul '04

20 Jul '04

*grin* its so obvious once you know the answer :-) Thx ----Original Message Follows---- On Tue, 20 Jul 2004, Crypt Master wrote: > Exmaple: > > <CODE> > type Fitness = Integer > data Population a = Population [(Fitness, a)] > deriving (Show) > > data GAParams = GAParams { randomNums :: [Integer] , > someFunc :: (Int->Int->(Population a))} > </CODE> Like for 'Population a' you have to specify a type parameter for 'GAParams', i.e. | v data GAParams a = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->(Population a))} _________________________________________________________________ Protect your PC - get McAfee.com VirusScan Online http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

1 0

How do I include polymorphic function type signatures in a data element ?
by Crypt Master 20 Jul '04

20 Jul '04

Hi How do I include polymorphic function type signatures in a data element ? Exmaple: <CODE> type Fitness = Integer data Population a = Population [(Fitness, a)] deriving (Show) data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->(Population a))} </CODE> This errors with parse input error on '}'. However something like this works fine: <CODE> data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->GAParams) } /<CODE> I am just having issues with polymorphic types. Any ideas ? The context is included below in case it helps: <CODE> import Random type Fitness = Integer data Population a = Population [(Fitness, a)] deriving (Show) data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->GAParams) } gaSolutionSpaceFrom :: Population a -> GAParams -> [Population a] gaSolutionSpaceFrom p gaParams = (evolvePopulation p gaParams) : gaSolutionSpaceFrom p newGAParams where (r,rs) = splitAt (length pl) (randomNums gaParams) Population pl = p newGAParams = (gaParams{randomNums=rs}) evolvePopulation :: Population a -> GAParams -> Population a evolvePopulation p gaParams = (mutate (cross (select p))) selectMatingPoolByRouletteWheel :: Population a -> GAParams -> Population a selectMatingPoolByRouletteWheel (Population popList) gaParams = (Population [ (rwSelect rw rnd) | rnd <- rndNums ]) where rw = createRW (Population popList) rndNums = (randomNums gaParams) rwSelect :: [(Fitness, a)] -> Fitness -> (Fitness, a) rwSelect [] _ = error "rwSelect random number outside roullete wheel range or list empty" rwSelect ((x,a):xs) z = if x <= z then rwSelect xs z else (x,a) createRW :: Population a -> [(Fitness, a)] createRW (Population xs) = (scanl1 f xs) where f (n,a) (m,b) = (n + m, a) select p = p cross p = p mutate p = p _________________________________________________________________ MSN 8 with e-mail virus protection service: 2 months FREE* http://join.msn.com/?page=features/virus

2 1

migrating from python
by paolo veronelli 14 Jul '04

14 Jul '04

I'm working on semantics and triples (RDF & co) Python code for inference in based totally on dictionaries (associative arrays ??),nested three or four times. The result is astonishing me:compact beautiful modular and extremely readable. I imagine that haskell way should be different but I'm in the dark. As the stream of triples coming from outside estabilishes the actions to be done for inference,the searching through keys (the words that form any triple) is the main job:every time I pick up a triple I have to enlarge the knowledge more or less "near" the resources represented by the words. And after I have produced (possibly) some new inferred triples surely I have to reswitch on some already read triples, matching a pattern. All these are very natural with dictionaries, so I'd like to figure out the haskell view. Thanks for your quiteness and answers Paolino -- ....lotta dura per la verdura

3 2

Process properties as global values
by Volker Wysk 12 Jul '04

12 Jul '04

Hi I'm just wondering, why haven't process properties (such as the command line arguments, or the parent process id), which are inherently global, been made global values in the Haskell standard? You could avoid needlessly carrying around these values, you wouldn't need to lift some functions into the IO monad... For instance, command line argument parsing could look something like this: import qualified System data ParsedArgs = ParsedArgs { pa_myflag :: Bool; ... } | Failure parsed_args :: ParsedArgs parsed_args = (... using System.argv ...) myflag = pa_myflag parsed_args main = do when (parsed_args == Failure) $ ... ... You can get the same effect by using unsafePerformIO. It would still be nice having this in the standard. Greetings, V.W. -- Volker Wysk <post(a)volker-wysk.de> http://www.volker-wysk.de

6 7

Giving up imperative habits....
by paolo veronelli 10 Jul '04

10 Jul '04

Usually I tend not to give much information to a subroutine intending to restrict its liberty of touching the calling information..... So if I have an instance Inst which should be changed by an outside-Inst computation Sub and I'm calling Sub with Sub(I'),I try to build the story so that Sub can only read Inst or a part of it (I') and return some specially structured information which then I use "inside" Inst to change Inst's state (horribble speech). The feeling I get with Haskell, is that S should have the freedom of changing I and return just I (changed). Is it any right ?? grazie Paolino -- ....lotta dura per la verdura

1 0

so how does one convert an IO a into an a ?
by Crypt Master 10 Jul '04

10 Jul '04

Hi Thanks for all the usefull responses, from theory to practical :-). I am busy digesting it all. I have more questions, but more and more I can answer them myself :-) Till the next misunderstanding ;-) C _________________________________________________________________ Add photos to your e-mail with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail

1 0