Re: [Haskell-cafe] A weird bug of regex-pcre
On Tue, Dec 18, 2012 at 02:28:26PM +0800, Magicloud Magiclouds wrote: Attachment is the test text file. And I tested my regexp as this: Prelude :m + Text.Regex.PCRE Prelude Text.Regex.PCRE z - readFile test.html Prelude Text.Regex.PCRE let (b, m ,a, ss) = z =~ a href=\(.*?)\.*?img class=\article-image\ :: (String, String, String, [String]) Prelude Text.Regex.PCRE b ... n of the Triumvirate/td\r\ntd class=\small\David Rapoza/td\r\n td class=\small\\r\n iReturn to Ravnica/i\r\n/td\r\n td class=\small\10/31/2012/td\r\n /trtr\r\n td class=\small\ Prelude Text.Regex.PCRE m a href=\/magic/magazine/article.aspx?x=mtg/daily/activity/1088\img class=\article-image\ From the value of b and m, it was weird that the matching was moved forward by 1 char ( the ss (sub matching) was even worse, 2 chars ). Rematch to a and so on gave correct results. It was only the first matching that was broken. Tested with regex-posix (with modified regexp), everything is OK. I have a similar issue with non-ascii strings. It seems that the internal representation used by Haskell and pcre are different and one of them is counting bytes and the other is counting code points. So they diverge when a multi-byte representation (like utf8) is used. It has been reported previously. See these threads: http://www.haskell.org/pipermail/haskell-cafe/2012-August/thread.html#102959 http://www.haskell.org/pipermail/haskell-cafe/2012-August/thread.html#103029 I am still waiting for a new release of regex-pcre that fixes this issue. Romildo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A weird bug of regex-pcre
I had similar issues a while ago. It had to do with UTF-8 encoding as far as I can recall. I wanted to wrap a multiline string (code listings) within some pandoc generated HTML of a hakyll page with a container div. The text to wrap would be determined using a PCRE regex. Here the (probably inefficient) implementation: module Transformations where import Hakyll import qualified Text.Regex.PCRE as RE import qualified Data.ByteString.UTF8 as BSU import qualified Data.ByteString as BS -- Wraps numbered code listings within the page body with a div -- in order to be able to apply some more specific styling. wrapNumberedCodelistings (Page meta body) = Page meta newBody where newBody = regexReplace' regex wrap body regex = table\\s+class=\sourceCode[^]+.*?/table- wrap x = div class=\sourceCodeWrap\ ++ x ++ /div -- Replace the whole string matched by the given -- regex using the given replacement function (hopefully UTF8-aware) regexReplace' :: String - (String - String) - String - String regexReplace' pattern replace text = BSU.toString $ go textUTF8 where patternUTF8 = BSU.fromString pattern textUTF8 = BSU.fromString text replaceUTF8 x = BSU.fromString $ replace $ BSU.toString x regex = RE.makeRegexOpts compOpts RE.defaultExecOpt $ BSU.fromString pattern compOpts = RE.compMultiline + RE.compDotAll + RE.compUTF8 + RE.compNoUTF8Check go part = case RE.matchM regex part of Just (before, match, after) - BS.concat [before, replaceUTF8 match, go after] _ - part The discussion back then was http://www.haskell.org/pipermail/beginners/2012-June/010064.html Hope this helps. Best regards, Rico Moorman P.S. Sorry for the double email Magicloud ... didn't hit reply all at first On Tue, Dec 18, 2012 at 10:43 AM, José Romildo Malaquias j.romi...@gmail.com wrote: On Tue, Dec 18, 2012 at 02:28:26PM +0800, Magicloud Magiclouds wrote: Attachment is the test text file. And I tested my regexp as this: Prelude :m + Text.Regex.PCRE Prelude Text.Regex.PCRE z - readFile test.html Prelude Text.Regex.PCRE let (b, m ,a, ss) = z =~ a href=\(.*?)\.*?img class=\article-image\ :: (String, String, String, [String]) Prelude Text.Regex.PCRE b ... n of the Triumvirate/td\r\ntd class=\small\David Rapoza/td\r\n td class=\small\\r\n iReturn to Ravnica/i\r\n /td\r\n td class=\small\10/31/2012/td\r\n /trtr\r\n td class=\small\ Prelude Text.Regex.PCRE m a href=\/magic/magazine/article.aspx?x=mtg/daily/activity/1088\img class=\article-image\ From the value of b and m, it was weird that the matching was moved forward by 1 char ( the ss (sub matching) was even worse, 2 chars ). Rematch to a and so on gave correct results. It was only the first matching that was broken. Tested with regex-posix (with modified regexp), everything is OK. I have a similar issue with non-ascii strings. It seems that the internal representation used by Haskell and pcre are different and one of them is counting bytes and the other is counting code points. So they diverge when a multi-byte representation (like utf8) is used. It has been reported previously. See these threads: http://www.haskell.org/pipermail/haskell-cafe/2012-August/thread.html#102959 http://www.haskell.org/pipermail/haskell-cafe/2012-August/thread.html#103029 I am still waiting for a new release of regex-pcre that fixes this issue. Romildo ___ 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
[Haskell-cafe] TAP 2013: 2nd Call for Papers
(Apologies if you receive this announcement multiple times.) *** *** *** TAP 2013*** *** *** *** Abstract submission: January 25, 2013 *** *** Paper submission:February 1, 2013 *** *** TAP 2013 solicits both full papers and *** *** (industrial) experience/tool papers *** *** in combining proofs and (security) testing *** CALL FOR PAPERS 7th INTERNATIONAL CONFERENCE ON TESTS AND PROOFS (TAP 2013) http://www.spacios.eu/TAP2013 Budapest, Hungary, June 18-19, 2013 The TAP conference is devoted to the synergy of proofs and tests, to the application of techniques from both sides and their combination for the advancement of software quality. Testing and proving seem to be contradictory techniques: once you have proved your program to be correct then additional testing seems pointless; on the other hand, when such a proof in not feasible, then testing the program seems to be the only option. This view has dominated the research community since the dawn of computer science, and has resulted in distinct communities pursuing the seemingly orthogonal research areas. However, the development of both approaches has lead to the discovery of common issues and to the realization of potential synergy. Perhaps, use of model checking in testing was one of the first signs that a counterexample to a proof may be interpreted as a test case. Recent breakthroughs in deductive techniques such as satisfiability modulo theories, abstract interpretation, and interactive theorem proving, have paved the way for new and practically effective methods of powering testing techniques. Moreover, since formal, proof-based verification is costly, testing invariants and background theories can be helpful to detect errors early and to improve cost effectiveness. Summing up, in the past few years an increasing number of research efforts have encountered the need for combining proofs and tests, dropping earlier dogmatic views of incompatibility and taking instead the best of what each of these software engineering domains has to offer. The TAP conference aims to bring together researchers and practitioners working in the converging fields of testing and proving, and will offer a generous allocation of papers, panels and informal discussions. Topics of interest cover theory definitions, tool constructions and experimentations, and include (other topics related to TAP are welcome): - Bridging the gap between concrete and symbolic techniques, e.g. using proof search in satisfiability modulo theories solvers to enhance various testing techniques - Transfer of concepts from testing to proving (e.g., coverage criteria) and from proving to testing - Program proving with the aid of testing techniques - New problematics in automated reasoning emerging from specificities of test generation - Verification and testing techniques combining proofs and tests - Generation of test data, oracles, or preambles by deductive techniques such as: theorem proving, model checking, symbolic execution, constraint logic programming - Model-based testing and verification - Generation of specifications by deduction - Automatic bug finding - Debugging of programs combining static and dynamic analysis - Formal frameworks - Tool descriptions and experience reports - Case studies combining tests and proofs - Domain specific applications of testing and proving to new application domains such as validating security protocols, vulnerability detection of programs, security Important Dates: Abstract submission: January 25, 2013 Paper submission: February 1, 2013 Notification: March 3, 2013 Camera ready version: April 5, 2013 TAP conference:June 17-21, 2013 Program Chairs: === Margus Veanes (Microsoft Research, USA) Luca Vigano` (University of Verona, Italy) Program Committee: == Paul Ammann Dirk Beyer Achim D. Brucker Robert Clarisò Marco Comini Catherine Dubois Gordon Fraser Angelo Gargantini Christoph Gladisch Martin Gogolla Arnaud Gotlieb Wolfgang Grieskamp Reiner Hähnle Bart Jacobs Thiérry Jeron Jacques Julliand Gregory Kapfhammer Nikolai Kosmatov Victor Kuliamin Michael Leuschel Karl Meinke Alexandre Petrenko Holger Schlingloff T.H. Tse Margus Veanes (co-chair) Luca Viganò (co-chair) Burkhart Wolff Fatiha Zaidi Submission: === Please submit your papers via easychair https://www.easychair.org/conferences/?conf=tap2013 TAP 2013 will accept two types of papers: - Research papers: full papers with at most 16 pages in LNCS format (pdf), which have to be original, unpublished and not submitted elsewhere. - Short contributions: work in progress, (industrial)
Re: [Haskell-cafe] A weird bug of regex-pcre
regex = table\\s+class=\sourceCode[^]+.*?/table- And mind the sneaky single - ... it doe not belong there ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HTF Quickcheck
Are there any libraries that define various common generators ? What would be the cleanest way to define two positive integers below 1000 that are different ? Seems relatively easy with conditionals. Thanks On Tue, Dec 18, 2012, at 07:01 AM, gra...@fatlazycat.com wrote: So what use are conditional properties meant to be used for ?? If you just want 2 integers that are not equal, it would seem a lot simpler to do this as a conditional rather than constructing some pair in an arbitrary instance ?!? Thanks On Mon, Dec 17, 2012, at 11:20 PM, Simon Hengel wrote: On Mon, Dec 17, 2012 at 06:04:15PM +0200, Roman Cheplyaka wrote: Unfortunately, I don't know the answer to your question. However, if you don't find a solution, I suggest using SmallCheck instead of QuickCheck — it works better when you have many unsuitable cases. https://github.com/feuerbach/smallcheck/wiki/Comparison-with-QuickCheck As far as I know, SmallCheck is not supported by HTF, but it is supported by test-framework. test-framework also sometimes thinks a Gave up! is not a fail, which I think is a bug. But I gave up on trying to get that fixed [1], e.g. this (admittedly contrived) property is still a pass with test-framework: defaultMain [testProperty foo $ \x - x == 23 == True] Cheers, Simon [1] https://github.com/batterseapower/test-framework/issues/16 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Race Condition in threads
Hello All I have two questions. 1. I wrote this code to create 10 simultaneous threads. Could some one please tell me if this is correct or not ? incr_count :: MVar () - MVar Int - IO () incr_count m n = ( forM_ [ 1..1 ] $ \_ - modifyMVar_ n ( return . ( + 10 ) ) ) putMVar m () main :: IO() main = do count - newMVar 0 list - forM [1..10] $ \_ - newEmptyMVar forM_ list $ \var - forkIO . incr_count var $ count forM_ list $ \var - takeMVar var val - takeMVar count print val 2. I am trying to create race condition which makes the variable in inconsistent state. Could some one please tell me how to achieve this ? I look at IORef but it does not have function like modifyMVar_. Mukesh Tiwari ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HTF Quickcheck
On Tue, Dec 18, 2012 at 05:25:41PM +, gra...@fatlazycat.com wrote: Are there any libraries that define various common generators ? What would be the cleanest way to define two positive integers below 1000 that are different ? Seems relatively easy with conditionals. You can still use (==) to ensure that two numbers are different. I would use something like this: newtype Small = Small Int deriving Show instance Arbitrary Small where arbitrary = Small . (`mod` 1000) $ arbitrary prop_foo (Small x) (Small y) = x /= y == ... Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Race Condition in threads
2012/12/18 mukesh tiwari mukeshtiwari.ii...@gmail.com: Hello All I have two questions. 1. I wrote this code to create 10 simultaneous threads. Could some one please tell me if this is correct or not ? incr_count :: MVar () - MVar Int - IO () incr_count m n = ( forM_ [ 1..1 ] $ \_ - modifyMVar_ n ( return . ( + 10 ) ) ) putMVar m () main :: IO() main = do count - newMVar 0 list - forM [1..10] $ \_ - newEmptyMVar forM_ list $ \var - forkIO . incr_count var $ count forM_ list $ \var - takeMVar var val - takeMVar count print val It is pretty much correct (some comments would be nice, though). 2. I am trying to create race condition which makes the variable in inconsistent state. Could some one please tell me how to achieve this ? I look at IORef but it does not have function like modifyMVar_. MVars are atomic in the sense that they have empty state and mutator can wait until variable will have a value. So you have to operate with something else, either IORef or with readMVar instead of takeMVar or modifyMVar_. Mukesh Tiwari ___ 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] Race Condition in threads
Hi Serguey Thank you for reply. I tried with IORef but I am missing a function which modify it. In this case every thread just write value 10 to variable n. incr_count :: MVar () - IORef Int - IO () incr_count m n = ( forM_ [ 1 .. 1 ] $ \_ - writeIORef n 10 ) putMVar m () main :: IO () main = do count - newIORef 0 list - forM [1..10] $ \_ - newEmptyMVar forM_ list $ \var - forkIO . incr_count var $ count forM_ list $ \var - takeMVar var val - readIORef count print val ghci:t atomicModifyIORef atomicModifyIORef :: IORef a - (a - (a, b)) - IO b ghci:t readIORef readIORef :: IORef a - IO a ghci:t writeIORef writeIORef :: IORef a - a - IO () I have atomicModifyIORef but it puts it into IO. I am missing some thing like this ghci:t modifyMVar_ modifyMVar_ :: MVar a - (a - IO a) - IO () modifyIORef_:: IORef a - ( a - IO a ) - IO () Mukesh Tiwari On Tue, Dec 18, 2012 at 11:50 PM, Serguey Zefirov sergu...@gmail.comwrote: 2012/12/18 mukesh tiwari mukeshtiwari.ii...@gmail.com: Hello All I have two questions. 1. I wrote this code to create 10 simultaneous threads. Could some one please tell me if this is correct or not ? incr_count :: MVar () - MVar Int - IO () incr_count m n = ( forM_ [ 1..1 ] $ \_ - modifyMVar_ n ( return . ( + 10 ) ) ) putMVar m () main :: IO() main = do count - newMVar 0 list - forM [1..10] $ \_ - newEmptyMVar forM_ list $ \var - forkIO . incr_count var $ count forM_ list $ \var - takeMVar var val - takeMVar count print val It is pretty much correct (some comments would be nice, though). 2. I am trying to create race condition which makes the variable in inconsistent state. Could some one please tell me how to achieve this ? I look at IORef but it does not have function like modifyMVar_. MVars are atomic in the sense that they have empty state and mutator can wait until variable will have a value. So you have to operate with something else, either IORef or with readMVar instead of takeMVar or modifyMVar_. Mukesh Tiwari ___ 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] HTF Quickcheck
Thanks, how does using /= not cause test failures ? Just the sample rate will be high enough ? On Tue, Dec 18, 2012, at 06:04 PM, Simon Hengel wrote: On Tue, Dec 18, 2012 at 05:25:41PM +, gra...@fatlazycat.com wrote: Are there any libraries that define various common generators ? What would be the cleanest way to define two positive integers below 1000 that are different ? Seems relatively easy with conditionals. You can still use (==) to ensure that two numbers are different. I would use something like this: newtype Small = Small Int deriving Show instance Arbitrary Small where arbitrary = Small . (`mod` 1000) $ arbitrary prop_foo (Small x) (Small y) = x /= y == ... Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] my Fasta is slow ;(
This time I have tried fasta benchmark since current entries does notdisplay
correct output.Program is copy of mine
http://benchmarksgame.alioth.debian.org/u64q/program.php?test=fastalang=gppid=1c++
benchmark, but unfortunately executes more than twice time.
Seems to me that culprit is in function random as I have tested rest of
codeand didn't found speed related problems.
bmaxa@maxa:~/shootout/fasta$ time ./fastahs 2500 /dev/null
real0m5.262suser0m5.228ssys 0m0.020s
bmaxa@maxa:~/shootout/fasta$ time ./fastacpp 2500 /dev/null
real0m2.075suser0m2.056ssys 0m0.012s
Since I am planning to contribute program, perhaps someone cansee a problem to
speed it up at least around 3.5 secs which is speed of bench that display
incorrect result (in 7.6.1).
Program follows:
{-# LANGUAGE BangPatterns #-}{- The Computer Language Benchmarks Game
http://shootout.alioth.debian.org/
contributed by Branimir Maksimovic-}
import System.Environmentimport System.IO.Unsafe
import Data.IORefimport Data.Array.Unboxedimport Data.Array.Storableimport
Data.Array.Baseimport Data.Word
import Foreign.Ptrimport Foreign.C.Types
type A = UArray Int Word8type B = StorableArray Int Word8type C = (UArray Int
Word8,UArray Int Double)
foreign import ccall unsafe stdio.h puts :: Ptr a - IO ()foreign
import ccall unsafe string.h strlen :: Ptr a - IO CInt
main :: IO () main = don - getArgs = readIO.head
let !a = (listArray (0,(length alu)-1) $ map (fromIntegral.
fromEnum) alu:: A)make ONE Homo sapiens alu (n*2) $ Main.repeat a
(length alu)make TWO IUB ambiguity codes (n*3) $ random iubmake
THREE Homo sapiens frequency (n*5) $ random homosapiens
make :: String - String - Int - IO Word8 - IO (){-# INLINE make #-}make id
desc n f = dolet lst = ++ id ++ ++ desca - (newListArray
(0,length lst) $ map (fromIntegral. fromEnum) lst:: IO B)
unsafeWrite a (length lst) 0pr amake' n 0where make' :: Int
- Int - IO ()make' !n !i = dolet line = (unsafePerformIO
$ newArray (0,60) 0 :: B)if n 0
then do!c - funsafeWrite line i c
if i+1 = 60 then do
pr linemake' (n-1) 0
else make' (n-1) (i+1)else do
unsafeWrite line i 0l - len line
if l /= 0then pr line
else return ()
pr :: B - IO ()pr line = withStorableArray line (\ptr - puts ptr)len :: B -
IO CIntlen line = withStorableArray line (\ptr - strlen ptr)
repeat :: A - Int - IO Word8repeat xs !n = dolet v = unsafePerformIO
$ newIORef 0!i - readIORef vif i+1 = nthen
writeIORef v 0else writeIORef v (i+1)return $ xs `unsafeAt`
i
random :: C - IO Word8random (a,b) = do !rnd - randlet
find :: Int - IO Word8find !i = let
!c = a `unsafeAt` i!p = b `unsafeAt` i
in if p = rndthen return celse
find (i+1)find 0
rand :: IO Double{-# INLINE rand #-}rand = do!seed - readIORef lastlet
newseed = (seed * ia + ic) `rem` imnewran = fromIntegral
newseed * rimdrimd = 1.0 / (fromIntegral im)im, ia, ic ::
Intim = 139968ia = 3877ic = 29573writeIORef last
newseedreturn newranwhere last = unsafePerformIO $ newIORef 42
alu:: [Char]alu = GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGG\
\GAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGA\
\CCAGCCTGGCCAACATGGTGAAAGTCTCTACTAT\
\ACATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCA\
\GCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGG\
\AGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCC\
\AGCCTGGGCGACAGAGCGAGACTCCGTCTCA
mkCum :: [(Char,Double)] - [(Word8,Double)]mkCum lst = map (\(c,p) -
((fromIntegral.fromEnum) c,p)) $ scanl1 (\(_,p) (c',p') - (c',
p+p')) lst
homosapiens, iub :: C
iub' = mkCum [('a',0.27),('c',0.12),('g',0.12),('t',0.27),('B',0.02)
,('D',0.02),('H',0.02),('K',0.02),('M',0.02),('N',0.02)
,('R',0.02),('S',0.02),('V',0.02),('W',0.02),('Y',0.02)]
homosapiens' = mkCum [('a',0.3029549426680),('c',0.1979883004921)
,('g',0.1975473066391),('t',0.3015094502008)]
iub = (listArray (0, (length iub')-1) $ map fst iub',listArray (0,
(length iub')-1) $ map snd iub')
homosapiens = (listArray (0, (length homosapiens')-1) $ map fst homosapiens',
listArray (0, (length homosapiens')-1) $ map snd homosapiens')
Re: [Haskell-cafe] Observer pattern in haskell FRP
Nathan Hüsken wrote:
On 12/08/2012 10:32 AM, Heinrich Apfelmus wrote:
Fair enough, but I don't see how this can be fitted into a general
pattern. If the animation state is coupled tightly to the game logic
state, then the question whether the animation is part of the game
logic or not does not have a clear answer anymore. Hm.
I see it like this: The logic state may not depend on the rendering
state. If for example the animation of an asteroid changes how or when
objects collide with it, than the animation is part of the logic.
If however the physics of the game treat the asteroid as a object whose
shape does not change depending in the animation, than the animation is
part of the rendering state.
So the coupling may only be logic-rendering.
Maybe discussing a concrete example could be very helpful. Could you
give a minimal example that still contains the key difficulties?
I put a pseudo C++ example below the mail. I use the terms model and
view for the game logic and rendering respectively.
The example is a little different. Asteroids explode when they collide.
The moment asteroids explode, they are removed from the model (the game
logic) while in the view (rendering) they still exist until the
explosion animation is over.
(Sorry for the late reply.)
I see, that's a nice example.
Indeed, if you try to model this situation with dynamic collections
galaxyModel :: Behavior [AsteroidModel]
galaxyView :: Behavior [AsteroidView]
then you have to keep track of IDs in some way, because a change in the
collection of asteroid models needs to be reflected in a corresponding
change in the collection of asteroid views.
identifier :: AsteroidModel - ID
eCollisions :: Event [ID]
eCollisions = collisions $ galaxyModel @ eTick
where
collisions asteroids = [identifier a | a - asteroids,
b - asteroids, a `collides` b]
galaxyModel = accumB initialAsteroidModels
$ removeFromList $ eCollisions
galaxyView = accumB initialAsteroidViews
$ startExplosions $ eCollisions
That said, do note that any significant use of pointers in an imperative
program translates to the use of identifiers in the purely functional
variant. This is very much *independent* of FRP! In other words, if you
find that giving certain game objects an identity is a good way to
structure your code, then you need to use identifiers, regardless of
whether you use FRP or not.
Of course, as you note in another message, there are other ways to
structure this code. For instance, the second idea would be to use a
data type
type Asteroid = (Maybe AsteroidModel, AsteroidView)
which represents live asteroids as (Just positionEtc, view) and dead
asteroids as (Nothing, explosionView) . Then again, one unsatisfactory
point about this approach is that an exploding asteroid is now
represented explicitly in the game logic as a Nothing value.
A third approach would be to keep an explicit list of explosions.
data AsteroidModel =
AsteroidModel { view :: AsteroidView, pos :: Position }
data AsteroidView =
AsteroidView { rotation :: Angle }
data Explosion =
Explosion { posExp :: Position }
galaxyView :: Behavior ([AsteroidView], [Explosion])
galaxyView = (,) $ (map view $ galaxyModel) $ explosions
explosions = accumB [] $ startExplosions $ eCollisions
You do need an event to communicate which asteroids have exploded, but
an exploding asteroid will not appear in galaxyModel anymore. Instead,
it will be added as an anonymous explosion to the rendering logic. (In
a sense, the asteroid views with the state variables dead = false and
dead = true have been split into different types.)
I find the third approach to be quite satisfactory. What is your opinion?
The more I think about this example, the more I think that the
underlying difficulty is not FRP, but the use of pointers / identities.
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On 12/17/2012 06:30 PM, Richard O'Keefe wrote: On 18/12/2012, at 3:45 PM, Christopher Howard wrote: It's basically the very old idea that an Abstract Data Type should be a nice algebra: things that look as though they ought to fit together should just work, and rearrangements of things ought not to change the semantics in surprising ways (i.e., Don't Be SQL). Categories contain two things: objects and arrows that connect objects. Some important things about arrows: - for any object x there must be an identity idx : x - x - any two compatible arrows must compose in one and only one way: f : x - y g : y - z = g . f : x - z - composition must be associative (f . g) . h = f . (g . h) when the arrows fit together. Of course for any category there is a dual category, so what I'm about to say doesn't really make sense, but there's sense in it somewhere: the things you are trying to hook together with your . operator seem to me more like objects than arrows, and it does not seem as if they hook together in one and only one way, so it's not so much _associativity_ being broken, as the idea of . being a composition in the first place. Since I received the two responses to my question, I've been trying to think deeply about this subject, and go back and understand the core ideas. I think the problem is that I really don't have a clear understanding of the basics of category theory, and even less clear idea of the connection to Haskell programming. I have been reading every link I can find, but I'm still finding the ideas of objects and especially morphisms to be quite vague. The original link I gave http://www.haskellforall.com/2012_08_01_archive.html purposely skipped over any discussion of objects, morphisms, domains, and codomains. The author stated, in his first example, that Haskell functions are a category, and proceeded to describe function composition. But here I am confused: If functions are a category, this would seem to imply (by the phrasing) that functions are the objects of the category. However, since we compose functions, and only morphisms are composed, it would follow that functions are actually morphisms. So, in the function category, are functions objects or morphisms? If they are morphisms, then what are the objects of the category? -- frigidcode.com signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Incremental regular expressions - article and library
Hi Haskellers, I just published an article that can be interesting to lovers of functional programming, even though it's not directly relevant to Haskell per se. http://jkff.info/articles/ire/ It's based on Dan Piponi's blogpost Fast incremental regular expression matching with monoids http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html but expands Dan's ideas to include *locating* matches, matching multiple regular expressions at once, using a more compact datastructure than fingertrees, etc. And - sorry - the implementation is in Java, for reasons explained in the article :) -- Eugene Kirpichov http://www.linkedin.com/in/eugenekirpichov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On Tue, Dec 18, 2012 at 11:03 PM, Christopher Howard The original link I gave http://www.haskellforall.com/2012_08_01_archive.html purposely skipped over any discussion of objects, morphisms, domains, and codomains. The author stated, in his first example, that Haskell functions are a category, and proceeded to describe function composition. But here I am confused: If functions are a category, this would seem to imply (by the phrasing) that functions are the objects of the category. However, since we compose functions, and only morphisms are composed, it would follow that functions are actually morphisms. So, in the function category, are functions objects or morphisms? If they are morphisms, then what are the objects of the category? Types. (P.S. Thanks Ertugrul, for giving me a way to latch onto the meaning of profunctors - now I'll have to go back to that package again and see if it makes more sense...) -- Your ship was destroyed in a monadic eruption. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On Tue, 18 Dec 2012, Christopher Howard wrote: On 12/17/2012 06:30 PM, Richard O'Keefe wrote: On 18/12/2012, at 3:45 PM, Christopher Howard wrote: It's basically the very old idea that an Abstract Data Type should be a nice algebra: things that look as though they ought to fit together should just work, and rearrangements of things ought not to change the semantics in surprising ways (i.e., Don't Be SQL). Categories contain two things: objects and arrows that connect objects. Some important things about arrows: - for any object x there must be an identity idx : x - x - any two compatible arrows must compose in one and only one way: f : x - y g : y - z = g . f : x - z - composition must be associative (f . g) . h = f . (g . h) when the arrows fit together. Of course for any category there is a dual category, so what I'm about to say doesn't really make sense, but there's sense in it somewhere: the things you are trying to hook together with your . operator seem to me more like objects than arrows, and it does not seem as if they hook together in one and only one way, so it's not so much _associativity_ being broken, as the idea of . being a composition in the first place. Since I received the two responses to my question, I've been trying to think deeply about this subject, and go back and understand the core ideas. I think the problem is that I really don't have a clear understanding of the basics of category theory, and even less clear idea of the connection to Haskell programming. I have been reading every link I can find, but I'm still finding the ideas of objects and especially morphisms to be quite vague. Much discussion that I have seen of categories and Haskell is imprecise. It is often possible to convey some fact, or point of view, using imprecise language, but in many cases, the communication will fail, unless the reader has a solid understanding of the basics. Getting this understanding requires studying harsh and, often, off putting, textbooks. I will say two things: 1. Usually, to understand category theory a firm grasp of the concept structure is required. 2. To connect categories with Haskell requires some apparatus, which apparatus should be laid out precisely, at least once in the exposition. ad 1: By a structure I mean what Bourbaki calls a structure. See: http://en.wikipedia.org/wiki/Mathematical_structure [page was last modified on 7 August 2012 at 17:15] http://en.wikipedia.org/wiki/Structure_%28mathematical_logic%29 [page was last modified on 15 December 2012 at 19:36] http://en.wikipedia.org/wiki/Algebraic_structure [page was last modified on 11 December 2012 at 02:51] ad 2: The tutorial should carefully distinguish these different things: a. the text of a Haskell program b. the binary of the now compiled program c. the running of the program d. the input output behavior of the program Each of these gives rise to at least one category, and there are various functors among these categories. Set theory, say ZFC style, and New Crazy Type Theory, offer two different Backround Mechanisms to explicate the notion of structure. There are similarities between these two Grand Theories, but there are also political differences. ad seeming vagueness of the notions object and morphism: This vagueness, which is felt by all students at first, is often explicated/excused by saying that the notions are more abstract than say, the notions of integer and addition of integers and multiplication of integers. This way of speaking is not entirely wrong, but I think it mainly wrong and misleading. Bourbaki somewhere says something like: Recent mathematics characteristically differs from older mathematics in that our axiom systems usually have more than one model, whereas in the old mathematics, theories usually had only one model. Here is how this explicates the sentence: The theory of rings is more abstract than the theory of addition and multiplication of the integers. We all know the integers. The integers form a set, with such elements as 0, 1, 17, -345, and so on. We have learned two operations on this single set: addition and multiplication. This understanding is a concrete understanding of a single concrete object, which does indeed have parts, such as -345, and the operation +, for example, but all the statements we might make can, in some sense, be settled by looking at this single structure and its various parts. Or so we feel. (Note in the sentence in which there are two occurences of the word concrete, the two occurences must have different sense.) But the theory of rings is quite a different theory. There are many different structures which are studied in the theory of rings. For example the ring of integers is one such structures. There is also the ring of complex numbers. There is also the ring of 2 x 2 matrices over the integers. Another ring is the ring of 3 x 3
Re: [Haskell-cafe] category design approach for inconvenient concepts
Christopher Howard christopher.how...@frigidcode.com wrote: Since I received the two responses to my question, I've been trying to think deeply about this subject, and go back and understand the core ideas. I think the problem is that I really don't have a clear understanding of the basics of category theory, and even less clear idea of the connection to Haskell programming. I have been reading every link I can find, but I'm still finding the ideas of objects and especially morphisms to be quite vague. It's vague on purpose, or in better words it's abstract. A category C is a collection of objects called ob(C) and a collection of morphisms hom(C) together with morphism composition that satisfies a few laws. That's it. It's up to you to interpret the objects and morphisms. Different categories give rise to completely different interpretations. What makes category theory interesting for programming is the set of laws, because unlike the unspecified nature of objects and morphisms, the laws are very specific. They establish a rigorous notion of soundness and locality. Let's review these laws: * For all f : A - B, g : B - A: id A . g = g f . id A = f This law is often understated. It means that identity morphisms are free of effects that could disturb composition. It also means that the composition does not change the nature of the component morphisms and is free of effects that could disturb the neutrality of identity morphisms. * f . (g . h) = (f . g) . h Not much to be said about this one, except that it makes composition 'lightweight' in a sense. This basically means that you don't care how compositions are grouped. These laws make morphisms isolated and composition lightweight as well as undisturbing. Now try to transfer these notions to a concrete category, for example the category of web servers: The objects are sets and a morphism f : A - B is a function from A × Request to B. The original link I gave http://www.haskellforall.com/2012_08_01_archive.html purposely skipped over any discussion of objects, morphisms, domains, and codomains. The author stated, in his first example, that Haskell functions are a category, and proceeded to describe function composition. But here I am confused: If functions are a category, this would seem to imply (by the phrasing) that functions are the objects of the category. However, since we compose functions, and only morphisms are composed, it would follow that functions are actually morphisms. So, in the function category, are functions objects or morphisms? If they are morphisms, then what are the objects of the category? You are absolutely right there. The category is common called Hask, the category of types and functions in Haskell. It is strongly related to the category of sets and functions, because Haskell types are actually just sets, where every set has one additional member: bottom. We say that the set is 'lifted'. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On 19/12/2012, at 11:03 AM, Christopher Howard wrote: Since I received the two responses to my question, I've been trying to think deeply about this subject, and go back and understand the core ideas. I think the problem is that I really don't have a clear understanding of the basics of category theory, and even less clear idea of the connection to Haskell programming. I have been reading every link I can find, but I'm still finding the ideas of objects and especially morphisms to be quite vague. Roughly speaking, Category Theory is the study of mathematical analogies that work. You notice that the symmetries of a cube have properties that remind you of the properties of integer addition, and end up constructing Group Theory to describe a huge range of things that can be modelled as things acted on by operations to give other things, where the operations follow particular laws. And you get this astonishing range of theorems that have lots of not-obviously-related applications. Then you notice that Group Theory and Lattice Theory and a bunch of other things seem to have more analogies than you expected, and you abstract out what they have in common (structured collections of things with transformations from one structure to another that preserve various properties of the structured collections). What's the connection to Haskell programming? Reusability. Both Category Theory and Haskell push rather harder on abstraction than most people are comfortable with, in order to get mathematical results in the one case and functional code in the other that can be applied to lots of problems. The price of reusability is vagueness. Let me offer an analogy. At primary school I was introduced to the greatest common divisor and Euclid's algorithm. Here's this algorithm that applies to integers and this is what it tells you. And in a program you might write gcd(x,y). These days, I look at gcd and see oh yes, the meet in the 'divides' lattice and write x/\y, where the same symbol (meet, /\) can be used for gcd, set intersection, bitwise and, unification, ...) and I know more _laws_ that /\ obeys than I did back then, but the integers have receded from view. The original link I gave http://www.haskellforall.com/2012_08_01_archive.html purposely skipped over any discussion of objects, morphisms, domains, and codomains. The author stated, in his first example, that Haskell functions are a category, and proceeded to describe function composition. This mailing list often talks about the Hask category. For example, in Orchard's blog (http://dorchard.wordpress.com) we find The Hask category The starting point of the idea is that programs in Haskell can be understood as providing definitions within some category, which we will call Hask. Categories comprise a collection of objects and a collection of morphisms which are mappings between objects. Categories come equipped with identity morphisms for every object and an associative composition operation for morphisms (see Wikipedia for a more complete, formal definition). For Hask, the objects are Haskell types, morphisms are functions in Haskell, identity morphisms are provided by the identity function, and composition is the usual function composition operation. In Hask, Haskell functions are the *morphisms* of a category, not its objects. That's not to say that you couldn't have a category whose objects were (in some sense) Haskell functions, just that it would be a different category. Rather confusingly, the objects of Hask are *not* data values, they are data *types*. This is just like the way that in the category of sets, the objects are *sets*, not their elements. But of course category theory is too general for a neat summary like objects are sets or types and morphisms are functions between them. No, objects are _whatever_ you choose to model as not-further-analysed objects, and morphisms are _whatever_ connections between your objects you choose to model as morphisms, so long as they obey the laws. I am struggling with category theory myself. I'll be learning about some kind of mathematical structure, getting to grips with the elements and the operations on the elements, and suddenly the book will move up a level and instead of looking at patterns between elements, will look at patterns of morphisms. And to add insult to injury, the book will claim that moving from one large space to an exponentially larger (if not worse) space remote from the things I'm trying to understand actually makes things _simpler_ to think about. One of my colleagues here divides people into set theory people and category theory people. He and I both classify ourselves as set theory people. Maybe in another 50 years I'll be comfortable with category theory, but by then I'll be dead. Right now, the issues for you are - Haskell people care about
Re: [Haskell-cafe] category design approach for inconvenient concepts
On Tue, Dec 18, 2012 at 4:49 PM, Ertugrul Söylemez e...@ertes.de wrote: These laws make morphisms isolated and composition lightweight as well as undisturbing. Now try to transfer these notions to a concrete category, for example the category of web servers: The objects are sets and a morphism f : A - B is a function from A × Request to B. Expanding on this point, we can refactor how we present this category, using laws from basic category theory, so that f :: (A, Request) - B f :: A - Request - B f :: A - (Request - B) f :: (A - Request) - B (this one isn't very useful to a programmer) f :: a - Request B (by lifting a concrete Request object into a functor of the form (Request a)) etc, are all equivalent, insofar as they merely present different interfaces to the same data. Note that these are distinct as presentations, but equivalent as categories (isomorphic, up to decidability -- the one I said wasn't useful really isn't, because as a matter of fact, we can't decidably analyze/deconstruct a function (g :: A - Request) to produce a B). This should make architectural decisions easy (or hard) -- once you have decided to use a category at all, you merely have to choose the presentation for the category that satisfies other requirements. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] efficient data structure: column with repeating values
Is there some good data type out there that basically provides a simple table, but with optimization for repeating values on one column? Something like: Data Table a b ...where it assumes that 'a' values will usually be unique, while 'b' values will usually be repeated from a small set? (But not needing to be fixed beforehand.) Like in... client | patron --- Bob| Tom Sarah | Tom Dick | Tom George | Harry Moe| Harry -- frigidcode.com signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On 12/17/12 9:45 PM, Christopher Howard wrote: However, what I'm wondering about is ideas that can be composed but that don't seem to fit the idea of category, because they don't obey the associativity law. To give a specific example (pseudo code like, without any idea here of implementation or proper syntax): Say you created a type called Component (C for short), the idea being to compose Components out of other Components. Every C has zero or more connectors on it. Two Cs can be connected to form a new C using some kind of composition operator (say, .), provided there are enough connectors (one on each). Presumably you would need a Fail constructor of some kind to represent the situation when there is not enough connectors. Say you had a C (coupler) with two connectors, a C (thing) with one connector, and a C (gadget) with one connector. So you could have... (coupler . thing) . gadget Because the coupler and the thing would combine to create a component with one spare connector. This would then combine with the gadget to make the final component. However, if you did... coupler . (thing . gadget) Then thing and gadget combine to make a component with no spare connectors. And so the new component and the coupler then fail to combine. Associativity law broken. So, can I adjust my idea to fit the category concept? Or is it just not applicable here? Or am I just misunderstanding the whole concept? I don't think you're describing a Category in the sense of the Haskell Category typeclass. But that's ok! Just because some things are categories and are nice doesn't mean that we can't have other nice things that aren't necessarily categories. My first thought was something with multiple inputs and one output is often an Operad (http://en.wikipedia.org/wiki/Operad_theory) but associativity is still an issue. Also bear in mind that operads and categories are both *directional* whereas your notion of coupling doesn't seem to be (which has something to do with associativity failing, I'd imagine). I also don't understand, e.g., what happens if I couple a thing with two connectors and one connector -- which connector from the first gets used, or are they interchangeable? Going back even further, you've suggested a Fail to represent when the connectors don't match. Why not start with encoding connectors in types to begin with, so that it is a type error to not have matching connectors? Follow the logic of your idea, shape your types to match your representable states, and then see what algebraic structures naturally emerge. Cheers, Gershom P.S. I think you're right to be confused by that article. It's confusingly written, and I think is a poor entry point into either category theory as such or even the proper use of the Category typeclass in Haskell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] efficient data structure: column with repeating values
Hi, just an idea (using Seq from Data.Seq and Map from Data.Map): newtype DataTable a b = DataTable (Map b (Seq a)) or if you know you won't have repeated values, you could have newtype DataTable a b = DataTable (Map b (Set a)) Both those ideas sort the data (partially or fully). If you need to preserve the ordering, you could do something like new DataTable a b = DataTable (Seq (a, Seq b)) Best regards, Petr Pudlak 2012/12/19 Christopher Howard christopher.how...@frigidcode.com Is there some good data type out there that basically provides a simple table, but with optimization for repeating values on one column? Something like: Data Table a b ...where it assumes that 'a' values will usually be unique, while 'b' values will usually be repeated from a small set? (But not needing to be fixed beforehand.) Like in... client | patron --- Bob| Tom Sarah | Tom Dick | Tom George | Harry Moe| Harry -- frigidcode.com ___ 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] A weird bug of regex-pcre
I see. A known bug. Thank you all. On Tue, Dec 18, 2012 at 10:11 PM, Rico Moorman rico.moor...@gmail.comwrote: regex = table\\s+class=\sourceCode[^]+.*?/table- And mind the sneaky single - ... it doe not belong there ;-) -- 竹密岂妨流水过 山高哪阻野云飞 And for G+, please use magiclouds#gmail.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] category design approach for inconvenient concepts
On 12/18/2012 08:02 PM, Gershom Bazerman wrote: On 12/17/12 9:45 PM, Christopher Howard wrote: I don't think you're describing a Category in the sense of the Haskell Category typeclass. But that's ok! Just because some things are categories and are nice doesn't mean that we can't have other nice things that aren't necessarily categories. My first thought was something with multiple inputs and one output is often an Operad (http://en.wikipedia.org/wiki/Operad_theory) but associativity is still an issue. Also bear in mind that operads and categories are both *directional* whereas your notion of coupling doesn't seem to be (which has something to do with associativity failing, I'd imagine). I think the example I gave was pretty messed up anyway, because I was trying to compose objects rather than morphisms. But that directional aspect you mentioned does seem significant... so I guess my main question is how that things that are more complex (like a multi-directional system built from pluggable components) could be represented in the Categorical manner. I'm looking for the Grand Unifying Theory to follow, if you will; I really like the idea that all parts of my program could be cleanly and systematically composed from smaller pieces, in some beautiful design patter. Many of the problems in my practical programming, however, are not like the examples I have seen (nice pipes or unidirectional calculations) but rather complex fitting together of components. E.g., space ships are made up of guns + engines + shields + ammo. Different kinds of space ships may use the same kind of guns (reusable components) but some wont. Some will have many guns, some will have none. And such like issues. Soylemez seems to have answered this issue directly in his reply. Unfortunately, I didn't understand most of what he wrote. :| I also don't understand, e.g., what happens if I couple a thing with two connectors and one connector -- which connector from the first gets used, or are they interchangeable? The example I gave was hastily put together and not well thought out. I was Just trying to come up with something that would convey the general idea. But perhaps each component would have a list of connectors, and the first ones in the list would be used first. When a new component was created from other components, the new list would be taken from the leftover connectors (if any). In real world use I would probably have multiple types of connectors, but I haven't thought that far ahead. Going back even further, you've suggested a Fail to represent when the connectors don't match. Why not start with encoding connectors in types to begin with, so that it is a type error to not have matching connectors? Follow the logic of your idea, shape your types to match your representable states, and then see what algebraic structures naturally emerge. Cheers, Gershom Sounds good. Of course, I still haven't figured out what design pattern to fit said types into. :( -- frigidcode.com signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
