### Re: [Haskell-cafe] Fwd: Re: Period of a sequence

On Mon, Jun 27, 2011 at 4:25 PM, Twan van Laarhoven twa...@gmail.comwrote: On 2011-06-27 13:51, Steffen Schuldenzucker wrote: Could you specify what exactly the function is supposed to do? I am pretty sure that a function like seqPeriod :: (Eq a) = [a] - Maybe Integer -- Nothing iff non-periodic cannot be written. What about sequences that can be specified in terms of 'iterate': This is beginning to be reminiscent of the recent paper by Max Bolingbroke, termination combinators forever (great paper). http://www.cl.cam.ac.uk/~mb566/papers/termination-combinators-hs11.pdf import Control.Arrow (first) -- Return the non-repeating part of a sequence followed by the repeating part. -- -- iterate f x0 == in a ++ cycle b -- where (a,b) = findCycle f x0 -- -- see http://en.wikipedia.org/wiki/**Cycle_detectionhttp://en.wikipedia.org/wiki/Cycle_detection findCycle :: Eq a = (a - a) - a - ([a],[a]) findCycle f x0 = go1 (f x0) (f (f x0)) where go1 x y | x == y= go2 x0 x | otherwise = go1 (f x) (f (f y)) go2 x y | x == y= ([], x : go3 x (f x)) | otherwise = first (x:) (go2 (f x) (f y)) go3 x y | x == y= [] | otherwise = y : go3 x (f y) -- diverges if not periodic seqPeriod :: Eq a = (a - a) - a - Integer seqPeriod f x0 = length . snd $ findCycle f x0 Twan __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://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] ANNOUNCE: doctest-0.3.0

On Thu, Jun 16, 2011 at 12:22 PM, Simon Hengel simon.hen...@wiktory.orgwrote: I just uploaded a new version of doctest[1] to Hackage. Sweet! I think using all lower-case package names is a good thing. I'm just curious -- why? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Exception for NaN

On Thu, May 12, 2011 at 5:50 PM, Daniel Fischer daniel.is.fisc...@googlemail.com wrote: Prelude Data.List maximum [0,-1,0/0,-5,-6,-3,0/0,-2] 0.0 Prelude Data.List minimum [0,-1,0/0,-5,-6,-3,0/0,-2] -2.0 Prelude Data.List sort [0,-1,0/0,-5,-6,-3,0/0,-2] [-6.0,-5.0,-2.0,NaN,-3.0,NaN,-1.0,0.0] Wow, that's the best example of NaN poison I've seen. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] How often is the planet updated?

On Thu, Apr 28, 2011 at 4:26 AM, Magnus Therning mag...@therning.orgwrote: I see that Planet Haskell hasn't been updated since April 26. Is something wrong with it, or does it really not update more often than that? In the past it has reliably updated within an hour of my publishing a new post. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Haskell from SML - referrential Transparency?!

On Tue, Apr 19, 2011 at 1:41 PM, Gregory Guthrie guth...@mum.edu wrote: Perhaps the description was unclear; F1;f1 gives result r1;r2 (not the same) F1;f2gives r1;r2 F2,f1gives r1;r2 No, you were clear, and Felipe's answer still makes sense. Since f1 and f2 have the same definition, substituting one for the other should not change anything. Maybe do notation is what is confusing you. Try getting rid of the do notation and writing everything in terms of the more basic () and (=) combinators. If () could be any operator, should we expect that f1 = f1 f1? Luke --- -Original Message- From: Felipe Almeida Lessa [mailto:felipe.le...@gmail.com] Sent: Tuesday, April 19, 2011 2:26 PM To: Gregory Guthrie Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Haskell from SML - referrential Transparency?! On Tue, Apr 19, 2011 at 4:10 PM, Gregory Guthrie guth...@mum.edu wrote: and I get different results from the two executions (f1,f2), even though they have exactly the same definition. Reversing their order, gives the exact same results (i.e. the results are still different, and in the same original order as f2;f1). Even doing (f1;f1) gives two different results. This shows that referential transparency is working nicely. -- Felipe. ___ 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] import functionality in DSLs

You can get away with this using {-# LANGUAGE RecordWildCards #-}, if you put your prelude into a record. Here's a test I did to make sure the technique worked: {-# LANGUAGE RecordWildCards #-} import Prelude hiding ((+)) data Foo = Foo { (+) :: Int - Int - Int, n0 :: Int } prelude :: IO Foo prelude = return $ Foo { (+) = (*), n0 = 1 } doit :: IO Int doit = do Foo{..} - prelude return $ n0 + 3 + 4 ghci doit 12 On Sat, Apr 16, 2011 at 7:29 AM, Nikhil A. Patil patil.nik...@gmail.comwrote: Hi, I am planning a simple monadic DSL (frankly, calling it a DSL is a bit of a stretch; it's just a somewhat glorified state monad), and I wish to implement some kind of import functionality for it. The DSL code looks something like this: doit :: DSL Term doit = do (+) - define_function + 2 n0 - define_constant 0 k - define_constant k -- begin beautiful DSL code let x = k + n0 return $ x + x The code above adds identifiers +, 0, k to the DSL monad and conveniently exposes haskell identifiers (+), n0, k for the user to use in code that follows. (Note that these define_* functions make state updates in the underlying state monad.) Needless to say, most functions like doit have very similar define_* calls in the beginning. Thus, I want to implement some kind of import functionality. Ideally, the code would look like this: module DSLPrelude where prelude :: DSL () prelude = do (+) - define_function + 2 n0 - define_constant 0 k - define_constant k return () module Main where import DSLPrelude doit :: DSL Term doit = do prelude -- begin beautiful DSL code let x = k + n0 return $ x + x ...but of course that won't work since (+), n0, k are not in scope. I can think of two solutions, both of which I dislike: Solution 1: module DSLPrelude where prelude :: DSL (Term - Term - Term, Term, Term) prelude = do (+) - define_function + 2 n0 - define_constant 0 k - define_constant k return ((+), n0, k) module Main where import DSLPrelude doit :: DSL Term doit = do ((+), k, n0) - prelude -- begin beautiful DSL code let x = k + n0 return $ x + x This is quite unsafe: I have mistakenly swapped k and n0 in doit, without failing typecheck. Solution 2: module DSLPrelude where (+) :: DSL (Term - Term - Term) n0 :: DSL Term k :: DSL Term (+) = define_function + 2 n0 = define_constant 0 k = define_constant k module Main where import DSLPrelude doit :: DSL Term doit = do (+) - (+) n0 - n0 k - k -- begin beautiful DSL code let x = k + n0 return $ x + x ...which works, but still has quite a bit of boilerplate crap. I feel this would be a common problem with a lot of DSLs, so I am curious to know how others solve it. Any pointers and suggestions are most welcome and greatly appreciated. Thanks! nikhil ___ 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] Programming Chalenges: The 3n+1 problem

On Thu, Apr 14, 2011 at 4:29 AM, Dmitri O.Kondratiev doko...@gmail.comwrote: 3n+1 is the first, warm-up problem at Programming Chalenges site: http://www.programming-challenges.com/pg.php?page=downloadproblemprobid=110101format=html (This problem illustrates Collatz conjecture: http://en.wikipedia.org/wiki/3n_%2B_1#Program_to_calculate_Collatz_sequences ) As long as the judge on this site takes only C and Java solutions, I submitted in Java some add-hock code (see at the end of this message) where I used recursion and a cache of computed cycles. Judge accepted my code and measured 0.292 sec with best overall submissions of 0.008 sec to solve the problem. *** Question: I wonder how to implement cache for this problem in Haskell? At the moment, I am not so much interested in the speed of the code, as in nice implementation. This is the exact problem data-memocombinators was written to solve. http://hackage.haskell.org/packages/archive/data-memocombinators/0.4.1/doc/html/Data-MemoCombinators.html For this problem, it is too slow to memoize everything; you have to use a bounded memo table. That's why I use a combinator-based memo approach as opposed to the type-directed approach used in eg. MemoTrie. The memo table you need is something like switch (10^6) integral id Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Deciding equality of functions.

On Sat, Apr 9, 2011 at 11:26 AM, Grigory Sarnitskiy sargrig...@ya.ruwrote: I guess that deciding whether two functions are equal in most cases is algorithmically impossible. However maybe there exists quite a large domain of decidable cases? If so, how can I employ that in Haskell? It is a common situation when one has two implementations of the same function, one being straightforward but slow, and the other being fast but complex. It would be nice to be able to check if these two versions are equal to catch bugs in the more complex implementation. Every function with a searchable domain and a decidable codomain has decidable equality. The classic example of a big searchable domain is the cantor space: import Data.Searchable type Nat = Int -- works with Integer too type Cantor = Nat - Bool bit :: Set Bool bit = doubleton True cantor :: Set Cantor cantor = fmap (!!) . sequence . repeat $ bit decEq :: (Eq a) = (Cantor - a) - (Cantor - a) - Bool decEq f g = forEvery (\c - f c == g c) So for example: ghci decEq ($ 4) ($ 4) True ghci decEq ($ 4) ($ 100) False ghci decEq (\c - c 4 c 42) (\c - not (not (c 4) || not (c 42))) True Searchable is based on work by Martin Escardo, very cool stuff. Data.Searchable comes from the infinite-search package. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Asynchronous Arrows need Type Specialization - Help!

On Sat, Apr 2, 2011 at 10:09 AM, Paul L nine...@gmail.com wrote: Sorry, forgot to CC the list. I wonder why Gmail doesn't default to reply-all. If you have keyboard shortcuts on, reply to messages with the a key instead of the r key. I hardly ever use r. Luke On Fri, Apr 1, 2011 at 9:48 PM, David Barbour dmbarb...@gmail.com wrote: If we ignore the 'delay' primitive (which lifts latency into program logic), my model does meet all the arrow laws. Nonetheless, the issues of physical synchronization still apply. It's important to recognize that the Arrow Laws do not describe non-functional properties, such as time-space performance. Well, when you throw the time stamp into the value domain, and according to your previous calculation of time stamps, (a1 *** a2) first a3 will produce different result than (a1 a3) *** a2. This is in direct conflict to arrow laws. Arrows by themselves do not impose physical synchronization. They are very often used to model computations about synchronous data streams, but that is a very different concept. In the actual implementation of such lifting (perhaps over multiple type classes), the calculation of the time stamp can be made precise. Indeed. And it is precisely the greater of the input timestamps. ;-) This is because you are using a single number as timestamp. Define your timestamp type differently, you'll get a different opinion. For example, you can use a pair of time stamps for pairs, and nested time stamps for nested values. -- Regards, Paul Liu ___ 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] working off a Yesod example file, need help lifting values from one monad into another. (and probably other things too).

On Mon, Mar 28, 2011 at 6:28 PM, Michael Litchard mich...@schmong.orgwrote: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 Ready or not, here I come. What is the purposes of these 368 numbers? Luke I'm working off of a example file from Yesod, ajax.lhs I've made an important change in types, and this has resulted in having to make the old code conform to the change. I will point out the specifics, then present my question. In the event I failed to include important information, I will paste in my code as well as the prototype. [Original] getHomeR :: Handler () getHomeR = do Ajax pages _ - getYesod let first = head pages redirect RedirectTemporary $ PageR $ pageSlug first [Changed] getHomeR :: Handler () getHomeR = do Tframe pages _ - getYesod let first = head pages redirect RedirectTemporary $ PageR $ pageSlug first Error Message test.lhs:62:4: Constructor `Tframe' should have 2 arguments, but has been given 1 In the pattern: Tframe pages In a stmt of a 'do' expression: Tframe pages - getYesod This is not what I wrote * In the expression: do { Tframe pages - getYesod; content - widgetToPageContent widget; hamletToRepHtml (hamlet-0.7.1:Text.Hamlet.Quasi.toHamletValue (do { (hamlet-0.7.1:Text.Hamlet.Quasi.htmlToHamletMonad . preEscapedString) !DOCTYPE htmlhtmlheadtitle; (hamlet-0.7.1:Text.Hamlet.Quasi.htmlToHamletMonad . Text.Blaze.toHtml) (Main.pageTitle content); })) } As far as I can tell, I only made a cosmetic change. I don't know what's going on here. [Original] data Page = Page { pageName :: String , pageSlug :: String , pageContent :: String I'm going to change this ** } [Changed] data Page = Page { pageTitle :: String , pageSlug :: String -- ^ used in the URL , pageContent :: IO String This is the change *** } Here's where I run into trouble [Original] json page = jsonMap [ (name, jsonScalar $ pageName page) , (content, jsonScalar $ pageContent page) I'm going to change this ] [My changes] json page = jsonMap [ (name, jsonScalar $ Main.pageTitle page) , (content, jsonScalar $ liftIO $ pageContent page) *** This is the change *** ] Here's the compiler error test.lhs:107:35: Couldn't match expected type `Char' against inferred type `[Char]' Expected type: String Inferred type: [String] In the second argument of `($)', namely `liftIO $ pageContent page' In the expression: jsonScalar $ liftIO $ pageContent page Failed, modules loaded: none. I'd appreciate a discussion about why this is wrong, and perhaps clues as to what is right. Last problem, stemming from the change in type to IO String. I don't have a clue as to what change I should make. test.lhs:100:25: No instance for (Text.Blaze.ToHtml (IO String)) arising from a use of `Text.Blaze.toHtml' at test.lhs:(100,25)-(103,3)

### Re: [Haskell-cafe] Tying the recursive knot

On Thu, Mar 24, 2011 at 4:02 PM, Joshua Ball joshbb...@gmail.com wrote: Never mind. I figured it out on my own. Here's my solution for posterity. There's probably a fix hiding in there somewhere - notice the new type of reduce. Yep, there is: force :: M.Map Key Chain - M.Map Key [Int] force mp = ret where ret = M.fromList (map (\k - (k, reduce mp (ret !) k)) (M.keys mp)) ^^^_^^^ There's your knot. You could have written it like this: force mp = fix (\ret - M.fromList (map (\k - (k, reduce mp (ret !) k)) (M.keys mp)) reduce :: M.Map Key Chain - (Key - [Int]) - Key - [Int] reduce mp lookup key = follow (mp ! key) where follow (Link i c) = i : follow c follow (Ref k) = lookup k follow (Trace message c) = trace message (follow c) example = M.fromList [(Key ones, Link 1 . Trace expensive computation here . Ref . Key $ ones)] main = print $ take 10 $ (force example ! Key ones) On Thu, Mar 24, 2011 at 12:35 PM, Joshua Ball joshbb...@gmail.com wrote: {- - Hi all, - - I'm having trouble tying the recursive knot in one of my programs. - - Suppose I have the following data structures and functions: -} module Recursion where import Control.Monad.Fix import Data.Map ((!)) import qualified Data.Map as M import Debug.Trace newtype Key = Key { unKey :: String } deriving (Eq, Ord, Show) data Chain = Link Int Chain | Trace String Chain | Ref Key deriving (Show) reduce :: M.Map Key Chain - Key - [Int] reduce env k = follow (env ! k) where follow (Link i c) = i : follow c follow (Ref k) = reduce env k follow (Trace message c) = trace message (follow c) -- Now I want a force function that expands all of the chains into int sequences. force1, force2 :: M.Map Key Chain - M.Map Key [Int] -- This is pretty easy to do: force1 mp = M.fromList (map (\k - (k, reduce mp k)) (M.keys mp)) -- But I want the int sequences to be lazy. The following example illustrates that they are not: example = M.fromList [(Key ones, Link 1 . Trace expensive computation here . Ref . Key $ ones)] -- Run force1 example in ghci, and you will see the expensive computation here messages interleaved with an infinite -- list of ones. I would prefer for the expensive computation to happen only once. -- Here was my first attempt at regaining laziness: fixpointee :: M.Map Key Chain - M.Map Key [Int] - M.Map Key [Int] fixpointee env mp = M.fromList (map (\k - (k, reduce env k)) (M.keys mp)) force2 env = fix (fixpointee env) main = print $ force2 example {- - However, this gets stuck in an infinite loop and doesn't make it past printing fromList . - (It was not difficult for me to see why, once I thought about it.) - - How do I recover laziness? A pure solution would be nice, but in the actual program - I am working on, I am in the IO monad, so I am ok with an impure solution. - It's also perfectly ok for me to modify the reduce function. - - Thanks in advance for you help, - Josh Ua Ball -} ___ 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 finite free category

On Wed, Mar 23, 2011 at 3:58 PM, Vasili I. Galchin vigalc...@gmail.com wrote: Hello, Does there exist Haskell to generate a finite free category from a finite multipath graph with loops? AKA the transitive closure of a graph? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] [Agda] Defining subtraction for naturals

If you are implementing lazy naturals, I wonder if defining 0 - 1 to be infinity makes mathematical sense. It's like arithmetic mod infinity Luke On Thu, Mar 17, 2011 at 12:35 PM, wren ng thornton w...@freegeek.org wrote: Another question on particulars. When dealing with natural numbers, we run into the problem of defining subtraction. There are a few reasonable definitions: (1) If the result would drop below zero then throw an overflow error; (2) Use saturating subtraction, i.e. if the result would drop below zero then return zero; (3) Use type hackery to disallow performing subtraction when the result would drop below zero, e.g. by requiring a proof that the left argument is not less than the right. Dependently typed languages tend to use the second definition because it gives a pure total function (unlike the first) and because it's less obnoxious to use than the third. In Haskell the third would be even more obnoxious. So my question is, mathematically speaking, is there any reason to prefer the second option over the first or third? Purity aside, I mean; do the natural numbers with saturating subtraction form any interesting mathematical object, or is it just what we're stuck with? In a similar vein. Given a finite set (e.g., the natural numbers with some finite upper bound) and assuming we've already decided not to use modular arithmetic, is there any mathematical reason to prefer saturating addition and/or multiplication instead of throwing an overflow error? -- Live well, ~wren ___ Agda mailing list a...@lists.chalmers.se https://lists.chalmers.se/mailman/listinfo/agda ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Type trickery

On Wed, Mar 16, 2011 at 7:52 AM, Andrew Coppin andrewcop...@btinternet.com wrote: Hmm, yes. That will work, but I wonder if there's some way of doing this that doesn't limit the scope of the container to one single span of code... You can write helper functions which take containers as argument by parameterizing these helper functions over s: takesTwoContainers :: Container s1 - Container s2 - ... takesTwoContainers c1 c2 = ... -- c1 and c2 can be used here This function could be called like this: withContainer (\c1 - withContainer (\c2 - takesTwoContainers c1 c2)) -- c1 and c2 can be used here In this example, the scope of the containers is not limited to a single span of code. What you can't do is write functions such as foo :: Container x - (Cursor x, Cursor x) for example. I don't follow. foo = cursor cursor Did you mean to have some extra condition on foo that can't be satisfied? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Reference monad

On Fri, Mar 11, 2011 at 8:18 PM, Joshua Ball scioli...@gmail.com wrote: Suppose I want the following functions: newRef :: a - RefMonad (Ref a) readRef :: Ref a - RefMonad a writeRef :: Ref a - a - RefMonad () Assuming this is a pure interface, you need one more thing: runRefMonad :: RefMonad a - a This little function creates a lot of big issues. For example: foo :: (Int, ()) foo = (runRefMonad (readRef ref), comp) where ref = runRefMonad (newRef 42) comp = runRefMonad (writeRef ref 32) What is the value of foo? This issue is solved by the type system trick of Control.Monad.ST, which is essentially the monad you describe. But it is not implemented purely (even though it has a pure interface). If you wanted to do it with a state monad and a Map, you have more problems than just garbage collection. You have to have a heterogeneous map, because different references can hold values of different types. There are three ways I am aware of of making a heterogeneous map: (1) allocating unique keys (requires the map to be in a ST-like existential context to be safe) and storing GHC.Prim.Anys in the map, and unsafeCoercing, relying on the type system to show that the unsafeCoerce is safe. (2) allocating unique keys (w/existential context) and storing Dynamics, then casting. Requires a (Typeable a) constraint on your operations, and is really just as unsafe as above (what do you do when the cast fails?) (3) keeping track of the keys in the type (a la hetero-map on hackage). Incompatible with the standard Monad class, which does not allow the type to change between binds. There may be more, of course. But so far they all seem to involve some sort of trickery. I would be delighted to see a pure, unsafe*-free implementation of your interface. I have never seen one, and I don't really expect it to exist. Likewise I would love to see a proof that it doesn't. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] ANN: theoremquest-0.0.0

On Mon, Feb 28, 2011 at 7:59 AM, Tom Hawkins tomahawk...@gmail.com wrote: I have been wanting to gain a better understanding of interactive theorem proving for some time. And I've often wondered: Can theorem proving be made into a user-friendly game that could attract mass appeal? And if so, could a population of gamers collectively solve interesting and relevant mathematical problems? I think this is an interesting project. This kind of thing has been on my mind recently. I haven't necessarily been thinking about how to publicize theorem proving, but I have been thinking about how to use computers to coordinate the efforts of mathematicians (including mere hobbyists like me). While our goals are not identical, they are certainly related. I was set on creating my own language for a while that would facilitate this, because I'm that kind of hubristic fellow. But I realized that it would probably be a better tactic to use an existing, more popular system, since I can leverage the existing work of others for a basis, and others already know their way around this system. It's easier to get critical mass starting from a few hundred than from one. But what I miss when using these proof assistants, and what I have my eyes on, is a way to Search ALL The Theorems. In current proof assistants, developments are still distributed in packages -- and a particular development might have already proved a very useful lemma that wasn't the main result, and if I'm doing something only barely related I will probably not find that package and have to prove that lemma again. I hope that a *good* theorem search engine would bump the level at which I do computer-assisted mathematics to nearly the level I do math in my head (conceptual, not technical). That may be a pipe dream. A theorem search engine I would consider good would have to solve a few technical problems: a big one is recognizing isomorphisms -- two people declared isomorphic structures and then proved some different results about them. We would like to be able to search for results about one and find results about the other. This is probably assisted by a user who proves the isomorphism between the two structures -- inferring isomorphisms automatically is probably too much to hope for. And then there's the issue of the highly overloaded word isomorphism -- there is no single definition, and results can be interchangeable in different ways appropriate in different contexts with different subtleties. Suffice to say I think your project is cool and I have my eye on it. Have you thought about searching? Luke To try to answer these questions -- and to gain some experience myself with theorem proving -- I started a project called TheoremQuest [1]. TheoremQuest intends to be a multi-player game system, where the game server receives requests by clients, such as theorem queries and inference rule applications. The TheoremQuest server validates deductions, compares them with existing theorems in the database, then returns results. TheoremQuest's deductive system borrows that of John Harrison's HOL Light [2]. There are 2 Hackage packages: theoremquest [3] is a library that declares types for terms, inference rules, and client-server transactions, used by both server and clients; and theoremquest-client [4] is an example client (tq). All the code, including the server-side, is hosted at github [5]. Currently the client-server interface is working, but little else. The library has defined most of the core inference rules, but has none of the basic types or axioms. And the tq client is nothing at all like a game; at this point it is just a command line tool to test the server. Currently tq can ping the server, create a new user, apply inference rules, and print out theorems. Here's how tq can prove x |- x: $ tq newuser tomahawkins tomahawk...@gmail.com Ack $ export THEOREMQUEST_USER=tomahawkins $ tq infer 'ASSUME (Var (Variable x Bool))' Id 1 $ tq theorem 1 assumptions: Var (Variable x Bool) conclusion: Var (Variable x Bool) I'd love to have help with this project, if anyone's interested. I'm still grappling with the logical core, but I think the real challenge will be creating game clients that are both capable and yet intuitive enough to appeal to the general population. If the masses can play Sudoku, shouldn't they be capable of interactive theorem proving? -Tom [1] http://theoremquest.org [2] http://www.cl.cam.ac.uk/~jrh13/hol-light/ [3] http://hackage.haskell.org/package/theoremquest [4] http://hackage.haskell.org/package/theoremquest-client [5] http://github.com/tomahawkins/theoremquest ___ 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] Fun with the ST monad

Lazy ST is capable of returning values lazily. Not naively -- eg. if you are writing elements to an STRef and then returning the contents of the STRef at the end, then of course it will not return gradually (who's to say that the last thing you do before you return isn't to write [] to the STRef?) However, if you do it this way: import Control.Monad.ST.Lazy import Data.STRef.Lazy main = print $ runST work where work = do ref - newSTRef 0 let loop = do x - readSTRef ref writeSTRef ref $! x+1 fmap (x:) loop loop You will find that it is perfectly lazy. You just have to communicate that the computation *must* yield an element regardless of what the remainder is. fmap (x:) rest is the typical way I yield elements from lazy ST. Luke On Thu, Feb 24, 2011 at 7:55 PM, Sterling Clover s.clo...@gmail.com wrote: On Feb 24, 2011, at 3:45 PM, Andrew Coppin wrote: OK, so I had a function that looks like transform :: [Word8] - [Word16] It works nicely, but I'd like to use mutable state inside. No problem! Use the ST monad. Something like transform :: [Word8] - [Word16] transform xs = runST (work xs) where work :: [Word8] - ST s [Word16] Ah, yes, well there is one *small* problem... If you do that, the function becomes too strict. unsafeInterleaveST? http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-ST.html#v:unsafeInterleaveST --Sterl ___ 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] monadic plumbing

On Tue, Feb 22, 2011 at 2:03 PM, Alberto G. Corona agocor...@gmail.com wrote: Recently I had to navigatate trough data structures chained with mutable referenes in th STM monad. The problem is that their values are enveloped in Either or Maybe results. functional compositions in the Either of Maybe , or list monads are not possible when the values are embedded inside effect monads (i.e. STM or IO) . I tried to find some trick to handle it. to summarize, given: foo, : a - m (Maybe b) bar : b - m (Maybe c) baz : c - m (Maybe d) These are isomorphic to: foo :: a - MaybeT m a And so on (from the MaybeT package on hackage). So to compose these three, lift them into MaybeT and then use Kleisli composition: MaybeT . foo = MaybeT . bar = MaybeT . baz Luke how to compose foo bar and baz? Or, at least, Are something out there to handle it in the less painful way?. I solved the generalized problem (chaining any double monadic combination) with a sort of monadic connector that acts as a double monadic operator == so that return. return (x :: a) == foo == bar == baz can be possible. Although I don't know if it is the best solution. I wonder why nobody has written about it before: class (Monad m, Monad n) = Bimonad m n where (=) :: n a - (a - m(n b)) - m(n b) (==) :: (Bimonad m n) = m (n a) - (a - m(n b)) - m (n b) (==) x f = x = \y - y = f x f = x == \ _- f infixl 1 ==, The instance for handling the Maybe monad under any other monad is very similar to the definition of the normal monad: instance (Monad m) = Bimonad m Maybe where Just x = f = f x Nothing = _ = return $ Nothing ___ 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] linear logic

On Tue, Feb 22, 2011 at 4:23 PM, Nick Rudnick joerg.rudn...@t-online.de wrote: Hi Vasili, not understanding clearly «in a categorical logic sense» -- but I can be sure you already checked out coherent spaces, which might be regarded as underlying Girard's original works in this sense?? I have a faint idea about improvements, but I don't have them present at the moment. Curiously -- is it allowed to ask about the motivation? Insofar as I'm curious is allowed as a legitimate response, yes. Luke Cheers, Nick On 02/22/2011 09:13 PM, Vasili I. Galchin wrote: Hello, What is the category that is used to interpret linear logic in a categorical logic sense? Thank you, Vasili ___ 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 mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Infinite types should be optionally allowed

On Sun, Feb 20, 2011 at 6:01 PM, Job Vranish jvran...@gmail.com wrote: My current algorithm says that neither of the types you gave is strictly more general than the other, which I'm guessing is probably not true. I'm curious what the correct answer is and would appreciate someone pointing out the flaw in my reasoning/code :) I don't remember how I constructed those terms, and I admit that I was arguing out of my depth. I really should have exposed my construction -- we're all good engineers here, we know the difference between an algorithm and intuition. Things I have read since have suggested that I was wrong. Pierce's Types and Programming Languages has a chapter on equi-recursive types which, if it does not provide insight itself, I'm sure has references to papers that go into all the detail needed to answer this technical question. Luke My test code is on github here: https://github.com/jvranish/InfiniteTypes Also, is there a book you'd recommend that would explain this in further detail? Thanks, - Job On Mon, Feb 16, 2009 at 5:16 PM, Luke Palmer lrpal...@gmail.com wrote: On Sat, Feb 14, 2009 at 2:06 PM, Job Vranish jvran...@gmail.com wrote: I'm pretty sure that the problem is decidable, at least with haskell 98 types (other type extensions may complicate things a bit). It ends up being a graph unification algorithm. I've tried some simple algorithms and they seem to work. What do you mean by the inference engine is only half of the story? From what I understand, the inference engine infers types via unification, if the types unify, then the unified types are the inferred types, if the types don't unify, then type check fails. Am I missing/misunderstanding something? Sorry it took me so long to respond. It took a while to formulate this example. Here are two (convoluted) functions, passed to the fixtypes inference engine: Expr y (b (c i) (c (b b (b c (c i) (fix b . (a - b - (a - c - d) - d) - c) - c Expr y (b (c i) (b (c (b b (b c (c i (b (c i) k))) (fix c . ((a - ((b - c) - d) - (a - d - e) - e) - f) - f) These are somewhat complex types; sorry about that. But here's a challenge: is one of these types more general than the other? For example, if you wrote the first term and gave the second signature, should it typecheck? If you figure it out, can you give an algorithm for doing so? I'm not going to say how I came up with these functions, because that would give away the answer :-) Luke I almost think that the problem might be solvable by just generating the appropriate newtype whenever an infinite type shows up, and doing the wrapping/unwrapping behind the scenes. This would be a hacked up way to do it, but I think it would work. On Fri, Feb 13, 2009 at 6:09 PM, Luke Palmer lrpal...@gmail.com wrote: On Fri, Feb 13, 2009 at 4:04 PM, Luke Palmer lrpal...@gmail.com wrote: On Fri, Feb 13, 2009 at 3:13 PM, Job Vranish jvran...@gmail.com wrote: There are good reasons against allowing infinite types by default (mostly, that a lot of things type check that are normally not what we want). An old haskell cafe conversation on the topic is here: http://www.nabble.com/There%27s-nothing-wrong-with-infinite-types!-td7713737.html However, I think infinite types should be allowed, but only with an explicit type signature. In other words, don't allow infinite types to be inferred, but if they are specified, let them pass. I think it would be very hard to shoot yourself in the foot this way. Oops! I'm sorry, I completely misread the proposal. Or read it correctly, saw an undecidability hiding in there, and got carried away. What you are proposing is called equi-recursive types, in contrast to the more popular iso-recursive types (which Haskell uses). There are plentiful undecidable problems with equi-recursive types, but there are ways to pull it off. The question is whether these ways play nicely with Haskell's type system. But because of the fundamental computational problems associated, there needs to be a great deal of certainty that this is even possible before considering its language design implications. That inference engine seems to be a pretty little proof-of-concept, doesn't it? But it is sweeping some very important stuff under the carpet. The proposal is to infer the type of a term, then check it against an annotation. Thus every program is well-typed, but it's the compiler's job to check that it has the type the user intended. I like the idea. But the inference engine is only half of the story. It does no type checking. Although checking is often viewed as the easier of the two problems, in this case it is not. A term has no normal form if and only if its type is equal to (forall a. a). You can see the problem here. Luke Newtype is the standard solution to situations where you really need an infinite

### Re: [Haskell-cafe] Can i split a String by its element ?

See the http://hackage.haskell.org/package/split package. You should be able to do this by splitting the string on comma, and then splitting the result on 0, plus some plumbing. Luke On Mon, Feb 21, 2011 at 11:46 PM, z_axis z_a...@163.com wrote: I want to split 2,15,33,0,8,1,16,18 to ([2,15,33],[8,1,16,18]). the 0 will by discarded. However, it seems that there isnot any standard function to do it. Sincerely! - e^(π.i) + 1 = 0 -- View this message in context: http://haskell.1045720.n5.nabble.com/Can-i-split-a-String-by-its-element-tp3395066p3395066.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.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] ANN: vector-buffer package 0.1

This interface is an outlaw. main = do buf - newBuffer 10 :: IO (Buffer Int) pushNextElement buf 1 let v1 = V.toList (toVector buf) v2 = V.toList (toVector buf) print v1 pushNextElement buf 2 print v2 Despite v1 and v2 being defined to equal the exact same thing, this program prints two distinct lines. toVector depends on the current state of the buffer. If this is to be a law-abiding interface, toVector must return a value in IO: toVector :: (Storable a) = Buffer a - IO (Vector a) Luke On Mon, Feb 14, 2011 at 7:28 PM, Alexander McPhail haskell.vivian.mcph...@gmail.com wrote: Hi, I have uploaded a small package, vector-buffer, to hackage. It provides a buffer that can be turned into a Data.Vector.Storable. The mapM* functions map from the oldest element, not the first. Similarly for the derived Vector. Feature requests etc. welcome. Vivian ___ 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] Proving correctness

On Fri, Feb 11, 2011 at 4:06 AM, C K Kashyap ckkash...@gmail.com wrote: Hi Folks, I've come across this a few times - In Haskell, once can prove the correctness of the code - Is this true? You can prove the correctness of code for any language that has precise semantics. Which is basically none of them (I believe a dialect of ML has one). But many languages come very close, and Haskell is one of them. In particular, Haskell's laziness allows very liberal use of equational reasoning, which is much more approachable as a technique for correctness proofs than operational semantics. The compiler is not able to verify your proofs, as Coq and Agda can, except in very simple cases. On the other hand, real-world programmers the advantage of not being forced to prove the correctness of their code because proofs are hard (technically Coq and Agda only require you to prove termination, but many times termination proofs require knowing most properties of your program so you have to essentially prove correctness anyway). I would like to see a language that allowed optional verification, but that is a hard balance to make because of the interaction of non-termination and the evaluation that needs to happen when verifying a proof. I have proved the correctness of Haskell code before. Mostly I prove that monads I define satisfy the monad laws when I am not sure whether they will. It is usually a pretty detailed process, and I only do it when I am feeling adventurous. I am not at home and I don't believe I've published any of my proofs, so you'll have to take my word for it :-P There is recent research on automatically proving (not just checking like QuickCheck, but formal proofs) stated properties in Haskell programs. It's very cool. http://www.doc.ic.ac.uk/~ws506/tryzeno/ I would not characterize provable code as an essential defining property of Haskell, though it is easier than in imperative and in strict functional languages. Again, Agda and Coq are really the ones that stand out in the provable code arena. And certainly I have an easier time mentally informally verifying the correctness of Haskell code than in other languages, because referential transparency removes many of the subtleties encountered in the process. I am often 100% sure of the correctness of my refactors. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] community server hasktags learned recursing into directories

On Fri, Feb 4, 2011 at 3:35 PM, Marc Weber marco-owe...@gmx.de wrote: hasktags learned about how to recurse into subdirectories itself. This is especially useful for windows because writing scripts can be done but is less well known (http://stackoverflow.com/questions/4865391/answer/submit) Now I'd like to push the latest changes to the community server which was hosting the repo in the past but my account does no longer work? Also there are some dead links now. Eg http://www.haskell.org/haskellwiki/Haskell.org_domain still references http://community.haskell.org/admin/ (404) Do you know what happened and where I should host the repo now? (uploading it to github would take seconds only) I host all my modules on github. It is a very supportive environment for spontaneous collaborative development. c.h.o is a nice place, but lacks in maturity in comparison. As long as there is a complete, free place like github around, why not use it? Luke Moreover I fonud that I was no longer subscribed to haskell-cafe. I can't remember having unsubscribed ? Let's hope this mail get's through now after having resubscribed. Marc Weber ___ 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] ($) not as transparent as it seems

This is probably a result of strictness analysis. error is technically strict, so it is reasonable to optimize to: let e = error foo in e `seq` error e On Thu, Feb 3, 2011 at 1:44 PM, Steffen Schuldenzucker sschuldenzuc...@uni-bonn.de wrote: Dear cafe, does anyone have an explanation for this?: error (error foo) *** Exception: foo error $ error foo *** Exception: *** Exception: foo -- Steffen ___ 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] Haskell for children? Any experience?

On Fri, Jan 28, 2011 at 10:47 AM, Chris Smith cdsm...@gmail.com wrote: Jason, thanks for the comments. Unfortunately, I probably won't do blogs about it. Hate to say it, but anyone who has read much outside of /r/haskell will surely agree it's irresponsible to write about children on Reddit. And things I write on my blog are likely to end up on Reddit. I have not read much outside of /r/haskell. Why is this irresponsible? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] H98, OOHaskell - getting started with objects in Haskell

On Mon, Jan 17, 2011 at 1:44 AM, Wolfgang Jeltsch g9ks1...@acme.softbase.org wrote: Am Sonntag, den 16.01.2011, 14:48 -0800 schrieb gutti: Looking at life u probably could save time, if u only would evaluate code on cells, where the neighbors have changed status. So rather than triggering them all centrally and each checks its neighbours, we could use the concept: - let the active ones trigger the neighbours so pass on activity But then you would have to take care to avoid cycles. You could also use on-demand updates with a centralized approach, and a centralized approach would probably make cycle detection easier. Don't forget about the double buffering you will need to do if you have a simultaneous rule. It doesn't take long before the dragons in imperative programming start messing with your easy specification. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Browser Game Engine

On Sun, Jan 16, 2011 at 8:26 PM, Tom Hawkins tomahawk...@gmail.com wrote: I want to create a simple browser game using Haskell. It would be nothing complicated: basic 2D graphics, limited sound, and minimal network traffic. What is the recommended medium? Flash or JavaScript+SVG? Unity3D is scriptable with Javascript and runs in browser. Not sure how difficult it would be to get the existing Javascript backends to interface with that library, but it's worth a shot. I highly recommend Unity3D, it's a very complete game development tool (and is just fine for 2D despite the name). Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Is this the right way to do polymorphism?

If you always expect to be passing c as a parameter and never returned, it is probably better off as a data type. Eg. HTTPClient might look like a traditional OO class: class HTTPClient c where foo :: c - stuff bar :: c - stuff I've found that it is easier to work with if you use a data type instead: data HTTPClient = HTTPClient { foo :: stuff, bar :: stuff } But other than that, yeah that's about right. If you want a function to be polymorphic in something, take the something as a parameter. Simple as that. Luke On Fri, Jan 7, 2011 at 8:01 PM, Daryoush Mehrtash dmehrt...@gmail.com wrote: I am trying to evaluate the polymorphism technique used in Hackage library. I like to know if the approach taken is right or not. The code in question is in the Hoaut package http://hackage.haskell.org/package/hoauth/ As far as I can understand the code wants to have polymorphism on HTTP client such that it can use different underlying HTTP. The package comes with Curl and Debug implementation of its HTTPClient class. My question is with how the polymorphism is used. In function such as serviceRequest in the Network.OAuth.Consumer module you have: -- | Performs a signed request with the available token. serviceRequest :: (HttpClient c,MonadIO m) = c - OAuthRequest - OAuthMonadT m Response serviceRequest c req = do { result - lift $ runClient c (unpackRq req) ; case (result) of Right rsp - return rsp Left err - fail $ Failure performing the request. [reason= ++ err ++] } The function expects the HTTPClient implementation to be the first argument to the function. Is that the right thing to do? Or should the instance of the client be a type parameter in the computation (in this case OAuthMonadT)? thanks, Daryoush ___ 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] Problem on overlapping instances

You can't. If you have special semantics for [String], then it is not really a [String], it is something else. So let the type system know that: newtype SomethingElse = SomethingElse [String] instance Binary SomethingElse where ... On Wed, Jan 5, 2011 at 1:24 AM, Magicloud Magiclouds magicloud.magiclo...@gmail.com wrote: Hi, I am using Data.Binary which defined instance Binary a = Binary [a]. Now I need to define instance Binary [String] to make something special for string list. How to make it work? I looked into the chapter of overlappinginstances, nothing works. -- 竹密岂妨流水过 山高哪阻野云飞 ___ 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 good video on monad

On Sun, Jan 2, 2011 at 11:48 PM, C K Kashyap ckkash...@gmail.com wrote: Hi, I found this nice video on monads (although for clojure). http://www.youtube.com/watch?v=ObR3qi4Guys Question - in the video, if I understood right, the guy implements return as a function that takes a value and returns a function (action) that takes nothing and returns that value. And upon executing the action (essentially invoking the function that takes void) you get the value. So, what is the correct way of thinking about the similarity(if any) between a function taking 0 parameters and a single parameter type constructor? Based on some of your phrasing, I think you are a Haskell beginner. Sorry if I misread -- if not, this message will be full of stuff you already know. I haven't watched the video, but I think I see the deeper question you are trying to ask. When you say function taking zero parameters I think you are referring to an action. In Haskell a function taking zero parameters is just a value. But in impure languages, or even in pure call-by-value languages, there is a distinction. You can make a type constructor corresponding to basically anything you want -- it's just a lambda abstraction over types with some extra syntax to help the compiler. Here's one corresponding to the second argument of a particular function type. newtype IntFunc2 a = IntFunc2 (Int - a - Int) Or the return value of a function. newtype IntFunc a = IntFunc (Int - a) There's one for plain old values: newtype Value a = Value a Which would be the Haskell version of your function taking zero arguments. But for impure languages, you might call something an action: newtype Action a = ??? Of course we cannot give a definition for a side-effectful action in a pure language, unless we precisely characterize the side-effects. But you can pretend the side-effects are characterized but we just don't know how -- and with this you get basically Haskell's IO type constructor. The similarity you are looking for begins to appear when you consider covariant type constructors, aka functors. Value, Action, IntFunc all have something in common: that you can map a function over their return value. mapValue :: (a - b) - Value a - Value b mapValue f (Value a) = Value (f a) mapIntFunc :: (a - b) - IntFunc a - IntFunc b mapIntFunc f (IntFunc f') = IntFunc (\x - f (f' x)) mapAction :: (a - b) - Action a - Action b mapAction f action = perform action and let x be the result, then yield f x A functor is a special kind of one parameter type constructor, that has one of these mapping operations (called fmap). It means that they treat their parameter in a particular way, roughly that they do something kind of like returning it rather than depending on it. Note that you cannot write such a definition for IntFunc2. So a type constructor representing a function taking 0 parameters in either a pure or an impure language, yields a functor on the return value, as does an action (when there is a difference). That functor is also applicative, and it also forms a monad, and lots of other stuff. But I thought functor would be especially relevant for some reason. I think the key point of enlightenment to be gleaned here is that, purely, there is a difference between a function taking 0 parameters and an action. These concepts only coincide when you allow functions to do things as well as return things, which Haskell does not. I apologize if this was a bit hard to follow, I was kind of shooting in the dark with this answer. I hope it gave some guidance. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] How about Haskell Golf just like vimgolf.com

On Mon, Jan 3, 2011 at 5:47 PM, Alex Kropivny alex.kropi...@gmail.com wrote: Could a subreddit of some kind be used for this, or is a new site necessary? Or maybe a stackexchange. While they are publicly going for big official branding sites, I get the impression that they would be open to a little thing like this. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] getting last char of String

http://haskell.org/hoogle/?hoogle=[Char]+-%3E+Char last looks conspicuous :-) On Fri, Dec 31, 2010 at 1:39 PM, Aaron Gray aaronngray.li...@gmail.com wrote: Is there an easy Haskell function that gets the last Char of a [Char] or String ? Many thanks in advance, Aaron ___ 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] What's the motivation for η rul es?

Eta conversion corresponds to extensionality; i.e. there is nothing more to a function than what it does to its argument. Suppose f x = g x for all x. Then using eta conversion: f = (\x. f x) = (\x. g x) = g Without eta this is not possible to prove. It would be possible for two functions to be distinct (well, not provably so) even if they do the same thing to every argument -- say if they had different performance characteristics. Eta is a controversial rule of lambda calculus -- sometimes it is omitted, for example, Coq does not use it. It tends to make things more difficult for the compiler -- I think Conor McBride is the local expert on that subject. On Tue, Dec 28, 2010 at 4:12 PM, David Sankel cam...@gmail.com wrote: TIA, David -- David Sankel Sankel Software www.sankelsoftware.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] IO, sequence, lazyness, takeWhile

On Mon, Dec 13, 2010 at 7:15 AM, Jacek Generowicz jacek.generow...@cern.ch wrote: -- Is it possible to rewrite code written in this style untilQuit = do text - getLine report text if text == quit then return () else untilQuit -- in a style using higher order functions for abstract iteration? For -- example, something along these lines: untilQuit' = (fmap (takeWhile (/= quit))) (sequence $ map (= report) (repeat getLine)) You are asking about standard library functions? Probably, but I think it is cleanest to just write a HOF to encapsulate this pattern. I have used this one before: whileM_ :: (Monad m) = (a - Bool) - m a - m () whileM_ p m = bool (return ()) (whileM p m) . p = m bool :: a - a - Bool - a bool t f True = t bool t f False = f untilQuit = whileM_ (/= quit) (getLine = liftM2 () report return) I find a variant of whileM that returns m [a] particularly handy for collecting events in an event loop. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Offer to mirror Hackage

On Wed, Dec 8, 2010 at 8:29 AM, C. McCann c...@uptoisomorphism.net wrote: On Wed, Dec 8, 2010 at 5:41 AM, Ketil Malde ke...@malde.org wrote: I'm a bit surprised to find that there seems to be a lot of opposition to this view, but perhaps the existing structure is more secure than I thought? The difference is in the ability to influence other packages and metadata, I think. You could upload a trojan to Hackage right now, but who would ever install it? I could upload a new version of mtl if I wanted. Plenty of people would install it. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Help defining a Typeable polymorphic-state monad transformer

This has nothing to do with a monad. This is just about data. You want a type that can contain any Typeable type, and a safe way to cast out of that type into the type that came in. Such a thing exists, it's called Data.Dynamic. Then your monad is just StateT Dynamic, where your magical maybeifying get is: getD :: (Monad m, Typeable a) = StateT Dynamic m a getD = maybe (fail Type error) return . cast = get Luke On Mon, Dec 6, 2010 at 9:09 PM, Brandon Simmons brandon.m.simm...@gmail.com wrote: Hi all, I gave myself until this evening to figure this out on my own, and time is up! Hopefully this makes for a good discussion, though the idea could be dumb. What I'm trying to do is define a state monad in which the passed state can change type during the computation. The only constraint is that the state types must always be of the Typeable class (see: http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Typeable.html ). The idea is that the new monad would be something like 'StateT s Maybe a', but where the 's' type is not fixed (indeed is hidden in an existential type) and where any programmer errors in the chaining of the polymorphic state will be caught in the Maybe type (or really the 'fail' implementation of any monad). Here is how I imagine a computation might look: computation :: TypeableState Maybe String computation = do (c:cs) - getTS putTS (length cs) return (c ++ was the first letter of the string passed as initial state.) So TypeableState is very similar to StateT, except that the state type is not present as a type argument. In the example above 'Maybe' is the monad that catches Typeable errors, and String is the return type of the computation. getTS and putTS would be get and put functions that constrain their arguments to the Typeable class. Here is what I have so far (at least this is my most recent uncommented attempt): {-# LANGUAGE ExistentialQuantification #-} module Main where import Control.Monad.State import Data.Typeable -- we might have restricted our 'm' to MonadPlus and used the explicit -- 'mzero', but decided instead to use Monad, with 'fail'. This is -- more appropriate since we won't be using 'mplus'. See 'liftMaybe'. data TypeableState m a = forall s0 sN. (Typeable s0, Typeable sN)= TypeableState (s0 - m (a,sN)) -- this is probably one of the more non-sensical attempts I've made at -- this... but I'm not sure: runTypeableState :: (Monad m, Typeable s0, Typeable sN)= TypeableState m a - s0 - m (a,sN) runTypeableState (TypeableState st) s0 = (liftMaybe $ cast s0) = st -- copied from Control.Monad.StateT instance (Monad m) = Monad (TypeableState m) where return a = TypeableState $ \s - return (a, s) m = k = TypeableState $ \s - do ~(a, s') - runTypeableState m s runTypeableState (k a) s' fail str = TypeableState $ \_ - fail str -- I imagine using this with 'cast' to thread the type in our monad -- transformer liftMaybe :: (Monad m)= Maybe a - m a liftMaybe = maybe (fail Monadic failure) return So is this even feasible? Or do I not grok what we can and can't do with the Typeable class? Any thoughts on this are appreciated. Sincerely, Brandon Simmons http://coder.bsimmons.name ___ 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] Interactive OpenGL-based graphics and ghci?

On Sat, Nov 20, 2010 at 4:46 PM, Conal Elliott co...@conal.net wrote: I'm trying to find some way to do interactive, OpenGL-based graphics in Haskell on Mac OS X. Does anyone here use GLUT or SDL on Mac OS X with ghci, or maybe an alternative library? I was reading the GHC 7 release notes and saw this: * There is a new -fno-ghci-sandbox flag, which stops GHCi running computations in a separate thread; in particular, this works around an issue running GLUT from GHCi on OS X So that seems to indicate that GLUT would fulfill your needs. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: ANNOUNCE zeno 0.1.0

Oops. It's right there on the site. My eyes skipped over it for some reason. On Sat, Nov 13, 2010 at 2:11 PM, Luke Palmer lrpal...@gmail.com wrote: Is the source code public, so I can run it on my own machine? Luke Hi all, My masters project Zeno was recently mentioned on this mailing list so I thought I'd announce that I've just finished a major update to it, bringing it slightly closer to being something useful. Zeno is a fully automated inductive theorem proving tool for Haskell programs. You can express a property such as takeWhile p xs ++ dropWhile p xs === xs and it will prove it to be true for all values of p :: a - Bool and xs :: [a], over all types a, using only the function definitions. Now that it's updated it can use polymorphic types/functions, and you express properties in Haskell itself (thanks to SPJ for the suggestion). It still can't use all of Haskell's syntax: you can't have internal functions (let/where can only assign values), and you can't use type-classed polymorphic variables in function definitions - you'll have to create a monomorphic instance of the function -but I hope to have these added reasonably soon. It's also still missing primitive-types/IO/imports so it still can't be used with any real-world Haskell code, it's more a bit of theorem proving fun. You can try it out at http://www.doc.ic.ac.uk/~ws506/tryzeno, the code file given there has some provable properties about a few prelude functions among other things. Another feature is that it lists all the sub-properties it has proven within each proof. When it verifies insertion-sort sorted (insertsort xs) === True it also proves the antisymmetry of = and that the insert function preserves the sorted property. Any suggestions or feedback would be greatly appreciated. Cheers, Will -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJM3kzdAAoJEC5dcKNjBzhn6ZgH/24Yy1TBsCCtwmvItROvucms VNlaJ9lAEwbFtQT4X0HJtBX0MaMc/2QcPXhXsTTXm5CG+28N7ohrVDz9WIn3Zmri Tet1c+NFeZ5s4dK9Xjc450r1zlBYu6Uc8y/z9+RRbUTdDKpifGScwoxqFQPeWWYX fUY9zfM6RW4W7A/hTzFIZlRpa2l8/1d4ojBeRw8PnxpPftBk8KvXAVBxq1Nf21Pc pKmcfMFfhTCPAXsroLMXzP22A51XhIXrSREpvE+OgDSHsoaO+0D2/q8VMV+J1zPw PPYvmM/BOYAPcjy/Z34kNv2g6letXKOjH5ofHREr5arHpsrsmJxP+rcveZWQi1A= =58nx -END PGP SIGNATURE- ___ 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] Re: ANNOUNCE zeno 0.1.0

Is the source code public, so I can run it on my own machine? Luke Hi all, My masters project Zeno was recently mentioned on this mailing list so I thought I'd announce that I've just finished a major update to it, bringing it slightly closer to being something useful. Zeno is a fully automated inductive theorem proving tool for Haskell programs. You can express a property such as takeWhile p xs ++ dropWhile p xs === xs and it will prove it to be true for all values of p :: a - Bool and xs :: [a], over all types a, using only the function definitions. Now that it's updated it can use polymorphic types/functions, and you express properties in Haskell itself (thanks to SPJ for the suggestion). It still can't use all of Haskell's syntax: you can't have internal functions (let/where can only assign values), and you can't use type-classed polymorphic variables in function definitions - you'll have to create a monomorphic instance of the function -but I hope to have these added reasonably soon. It's also still missing primitive-types/IO/imports so it still can't be used with any real-world Haskell code, it's more a bit of theorem proving fun. You can try it out at http://www.doc.ic.ac.uk/~ws506/tryzeno, the code file given there has some provable properties about a few prelude functions among other things. Another feature is that it lists all the sub-properties it has proven within each proof. When it verifies insertion-sort sorted (insertsort xs) === True it also proves the antisymmetry of = and that the insert function preserves the sorted property. Any suggestions or feedback would be greatly appreciated. Cheers, Will -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJM3kzdAAoJEC5dcKNjBzhn6ZgH/24Yy1TBsCCtwmvItROvucms VNlaJ9lAEwbFtQT4X0HJtBX0MaMc/2QcPXhXsTTXm5CG+28N7ohrVDz9WIn3Zmri Tet1c+NFeZ5s4dK9Xjc450r1zlBYu6Uc8y/z9+RRbUTdDKpifGScwoxqFQPeWWYX fUY9zfM6RW4W7A/hTzFIZlRpa2l8/1d4ojBeRw8PnxpPftBk8KvXAVBxq1Nf21Pc pKmcfMFfhTCPAXsroLMXzP22A51XhIXrSREpvE+OgDSHsoaO+0D2/q8VMV+J1zPw PPYvmM/BOYAPcjy/Z34kNv2g6letXKOjH5ofHREr5arHpsrsmJxP+rcveZWQi1A= =58nx -END PGP SIGNATURE- ___ 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] Ralf Laemmel's riddle on surviving without the monad transformation library

I haven't watched the lecture. But what does he mean survive? Does it mean to do anything that you can do with mtl? On Mon, Nov 15, 2010 at 12:53 AM, C K Kashyap ckkash...@gmail.com wrote: Hi, Can someone provide me the solution to the following riddle that Ralf asked in his lecture at http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Dr-Ralf-Lmmel-Advanced-Functional-Programming-Evolution-of-an-Interpreter Riddle: define a custom made monad (only involving (-) and Either String) to survive without the monad transformation library. -- Regards, Kashyap ___ 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] Re: ANNOUNCE zeno 0.1.0

I guess I'm not on the list that received the original announce. But I have to say, I played with the demo ( http://www.doc.ic.ac.uk/~ws506/tryzeno/ ). Wow! I am delighted and impressed, and I think this is a huge step forward. Great work! Luke On Sat, Nov 13, 2010 at 1:31 AM, Petr Pudlak d...@pudlak.name wrote: Hi Will, I was wondering, Zeno capable of proving just equational statements, or is it able to prove more general statements about programs? In particular, it would be interesting if Zeno would be able to prove that a function is total by verifying that it uses only structural (inductive) recursion (on a well defined inductive type), i.e. each recursive function call must be on a syntactic subcomponent of its parameter. And dually, one might want to prove that a function is corecursive, meaning that each recursive call is guarded by a constructor. Best regards, Petr Hi all, My masters project Zeno was recently mentioned on this mailing list so I thought I'd announce that I've just finished a major update to it, bringing it slightly closer to being something useful. Zeno is a fully automated inductive theorem proving tool for Haskell programs. You can express a property such as takeWhile p xs ++ dropWhile p xs === xs and it will prove it to be true for all values of p :: a - Bool and xs :: [a], over all types a, using only the function definitions. Now that it's updated it can use polymorphic types/functions, and you express properties in Haskell itself (thanks to SPJ for the suggestion). It still can't use all of Haskell's syntax: you can't have internal functions (let/where can only assign values), and you can't use type-classed polymorphic variables in function definitions - you'll have to create a monomorphic instance of the function -but I hope to have these added reasonably soon. It's also still missing primitive-types/IO/imports so it still can't be used with any real-world Haskell code, it's more a bit of theorem proving fun. You can try it out at http://www.doc.ic.ac.uk/~ws506/tryzeno, the code file given there has some provable properties about a few prelude functions among other things. Another feature is that it lists all the sub-properties it has proven within each proof. When it verifies insertion-sort sorted (insertsort xs) === True it also proves the antisymmetry of = and that the insert function preserves the sorted property. Any suggestions or feedback would be greatly appreciated. Cheers, Will -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJM3kzdAAoJEC5dcKNjBzhn6ZgH/24Yy1TBsCCtwmvItROvucms VNlaJ9lAEwbFtQT4X0HJtBX0MaMc/2QcPXhXsTTXm5CG+28N7ohrVDz9WIn3Zmri Tet1c+NFeZ5s4dK9Xjc450r1zlBYu6Uc8y/z9+RRbUTdDKpifGScwoxqFQPeWWYX fUY9zfM6RW4W7A/hTzFIZlRpa2l8/1d4ojBeRw8PnxpPftBk8KvXAVBxq1Nf21Pc pKmcfMFfhTCPAXsroLMXzP22A51XhIXrSREpvE+OgDSHsoaO+0D2/q8VMV+J1zPw PPYvmM/BOYAPcjy/Z34kNv2g6letXKOjH5ofHREr5arHpsrsmJxP+rcveZWQi1A= =58nx -END PGP SIGNATURE- ___ 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] Splittable random numbers

On Fri, Nov 12, 2010 at 3:33 AM, Richard Senington sc06...@leeds.ac.uk wrote: In short, I am worried by the properties of this random number generator. I propose improving the testing system, and then posting both the test suite and this random generator to Hackage, unless you really want it up now in a very very preliminary form. Yeah I think a package of randomness tests could be really useful. Cool :-) RS import System.Random data LehmerTree = LehmerTree {nextInt :: Int, leftBranch :: LehmerTree, rightBranch :: LehmerTree} instance Show LehmerTree where show g = LehmerTree, current root = ++(show $ nextInt g) mkLehmerTree :: Int-Int-Int-Int-Int-Int-LehmerTree mkLehmerTree aL aR cL cR m x0 = innerMkTree x0 where mkLeft x = (aL * x + cL) `mod` m mkRight x = (aR * x + cR) `mod` m innerMkTree x = let l = innerMkTree (mkLeft x) r = innerMkTree (mkRight x) in LehmerTree x l r mkLehmerTreeFromRandom :: IO LehmerTree mkLehmerTreeFromRandom = do gen-getStdGen let a:b:c:d:e:f:_ = randoms gen return $ mkLehmerTree a b c d e f This can be pure: mkLehmerTreeFromRandom :: (RandomGen g) = g - LehmerTree instance RandomGen LehmerTree where next g = (fromIntegral.nextInt $ g, leftBranch g) split g = (leftBranch g, rightBranch g) genRange _ = (0, 2147483562) -- duplicate of stdRange test :: IO() test = do gen-mkLehmerTreeFromRandom print gen let (g1,g2) = split gen let p = take 10 $ randoms gen :: [Int] let p' = take 10 $ randoms g1 :: [Int] -- let p'' = take 10 $ randoms g2 :: [Float] print p print p' -- print p'' ___ 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] Serialization of (a - b) and IO a

On Thu, Nov 11, 2010 at 12:53 AM, Jesse Schalken jesseschal...@gmail.com wrote: I have had a look at hs-plugins, but it is unclear how to derive a simple pair of functions `(a - b) - ByteString` and `ByteString - Either ParseError (a - b)`, for example, from the functionality it provides, if it is possible at all. I guess such a thing requires thorough digging into the depths of GHC, (or maybe even LLVM if an architecture independent representation is sought, but I don't know enough to say.). Perhaps this is more a question for those interested and knowledgable in Haskell compilation (and, to some extent, decompilation). If not Haskell, are there any languages which provide a simple serialization and deserialization of functions? As far as I know, GHC has no support for this. There are issues with the idea that will come out pretty fast, such as: (1) Those cannot be pure functions, because it differentiate denotationally equal functions. So it would have to be at least (a - b) - IO ByteString. (2) What if you tried to serialize a filehandle or an FFI Ptr? But my answers are Ok and Then you get a runtime error, respectively. It is by no means impossible, IIRC Clean does it. I think it's pretty dumb that we don't have support for this yet. Purely functional languages have a unique disposition to be very good at this. But oh well, there aren't enough tuits for everything. A more elaborate answer to (2) is you get a runtime error when you try to *use* the thing that was impossible to serialize. This makes sure that you don't get an error if you are trying to serialize \x - const x a_filehandle_or_something, which is just the identity function. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Type Directed Name Resolution

On Thu, Nov 11, 2010 at 1:34 AM, John Lask jvl...@hotmail.com wrote: On 11/11/2010 5:21 PM, Ketil Malde wrote: Richard O'Keefeo...@cs.otago.ac.nz writes: it is often desirable to have the same field names for many records in the same module. very much so, this is currently possible, with the restriction that the field names must have the same type modulo the record it is selecting on. what is disirable is that this restriction be lifted. Haskell has a wonderful history of being careful to consider both sides of a restriction. One one hand, a restriction can make it harder to write something you want to write. On the other hand, a restriction can provide properties that make it easy to transform and reason about your program. So I am not ready to accept your claim that this is desirable without further justification. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Type Directed Name Resolution

On Thu, Nov 11, 2010 at 1:41 AM, Luke Palmer lrpal...@gmail.com wrote: On Thu, Nov 11, 2010 at 1:34 AM, John Lask jvl...@hotmail.com wrote: On 11/11/2010 5:21 PM, Ketil Malde wrote: Richard O'Keefeo...@cs.otago.ac.nz writes: it is often desirable to have the same field names for many records in the same module. very much so, this is currently possible, with the restriction that the field names must have the same type modulo the record it is selecting on. what is disirable is that this restriction be lifted. Haskell has a wonderful history of being careful to consider both sides of a restriction. One one hand, a restriction can make it harder to write something you want to write. On the other hand, a restriction can provide properties that make it easy to transform and reason about your program. So I am not ready to accept your claim that this is desirable without further justification. Sorry for the self-reply. I just want to clarify, I didn't mean to write off your well-thought-out message with this simple comment. I was just drawing attention to the duality of restrictions. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Splittable random numbers

On Thu, Nov 11, 2010 at 3:13 AM, Richard Senington sc06...@leeds.ac.uk wrote: I got hold of, and looked through the paper suggested in the root of this thread “Pseudo random trees in Monte-Carlo, and based upon this I have thrown together a version of the binary tree based random number generator suggested. I would like to point out that I do not know very much about random number generators, the underlying mathematics or any subsequent papers on this subject, this is just a very naive implementation based upon this one paper. As a question, the following code actually generates a stream of numbers that is more random than I was expecting, if anyone can explain why I would be very interested. What do you mean more random than you were expecting? Shouldn't they be maximally random? BTW, nice module. Do you want to hackage it up? If not, I will. import System.Random data LehmerTree = LehmerTree {nextInt :: Int, leftBranch :: LehmerTree, rightBranch :: LehmerTree} instance Show LehmerTree where show g = LehmerTree, current root = ++(show $ nextInt g) mkLehmerTree :: Int-Int-Int-Int-Int-Int-LehmerTree mkLehmerTree aL aR cL cR m x0 = innerMkTree x0 where mkLeft x = (aL * x + cL) `mod` m mkRight x = (aR * x + cR) `mod` m innerMkTree x = let l = innerMkTree (mkLeft x) r = innerMkTree (mkRight x) in LehmerTree x l r mkLehmerTreeFromRandom :: IO LehmerTree mkLehmerTreeFromRandom = do gen-getStdGen let a:b:c:d:e:f:_ = randoms gen return $ mkLehmerTree a b c d e f This can be pure: mkLehmerTreeFromRandom :: (RandomGen g) = g - LehmerTree instance RandomGen LehmerTree where next g = (fromIntegral.nextInt $ g, leftBranch g) split g = (leftBranch g, rightBranch g) genRange _ = (0, 2147483562) -- duplicate of stdRange test :: IO() test = do gen-mkLehmerTreeFromRandom print gen let (g1,g2) = split gen let p = take 10 $ randoms gen :: [Int] let p' = take 10 $ randoms g1 :: [Int] -- let p'' = take 10 $ randoms g2 :: [Float] print p print p' -- print p'' ___ 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] Serialization of (a - b) and IO a

On Thu, Nov 11, 2010 at 6:16 PM, Dan Doel dan.d...@gmail.com wrote: serialize is not at all the same in this regard. There is no class of functions that is immune to its inspection powers, presumably, because that's its whole point. But that also means that there is no class of functions for which we are justified in reasoning equationally using the standard extensional equality. The only way that would be justified is saying, serialize doesn't exist. Admittedly, the class of reasoning I usually use in my Haskell programs, and the one that you talked about using earlier this message, is essentially seq doesn't exist. However, I prefer to use this class of reasoning because I would prefer if seq actually didn't exist (er, I think the implication goes the other way). Not so for serialize: I would like a serialize function, but I don't want the semantic burden it brings. If only there were a way to... oh yeah. serialize :: (a - b) - IO String I still don't really get what we're arguing about. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] What is simplest extension language to implement?

On Thu, Nov 4, 2010 at 5:30 AM, Malcolm Wallace malcolm.wall...@me.com wrote: ehm. I missed something and ghc api is well documented and stable ? There are other ways of adding Haskell as a scripting language - bundling ghc is not necessary. Do tell. It is inacceptable for scripting language, faced to no-programmers. Such languages must be as plain and regular, as possible. We give Haskell as a embedded scripting language to non-programmers, and they love it. They especially like the strong typing, which finds their bugs before they ever get the chance to run their script. The terseness and lack of similarity to other programming languages is another benefit. Regards, Malcolm ___ 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] Re: Haskell is a scripting language inspiredby Python.

On Thu, Nov 4, 2010 at 6:00 PM, Donn Cave d...@avvanta.com wrote: I don't care about whether Python had any influence, but I'd sure like to stamp out the scripting language rumor. You all are talking about calling Haskell a scripting language like it's a bad thing. Coming from a Perl background, I learned that when a culture made stuck-up claims about its language being a real programming language, what it meant was that it would be verbose, dry, and no fun. To us, scripting meant short, potent code that rolled off your fingers and into the computers mind, compelling it to do your job with reverence to the super power you truly are. Programming meant a system with 100,000 lines of boring code that reinvents a broken dialect of LISP because it was too rigid to get the job done naturally. I also have a C++ background and a C# foreground. This large, inert culture views Programs with a capital P as large, complete tools like Photoshop (also with a capital P). Their #1 stigma against scripting languages is that they are too slow to do real work. Also they don't scale well, which I guess means that they don't make it inconvenient to design badly. Haskell is a language in which it is possible to write short, potent code (I use it at the command line). It is fast enough to do real work. It is inconvenient to design badly. It is fun. It is also dry sometimes. Scripting language strikes me as one of those terms that is used in heated arguments despite having no meaning (meaningless terms seem to proliferate as the heat is turned up). I dunno, I just don't think it is a big deal. Everybody seems to be calling Haskell a DSL-writing language, but that can just as easily be taken as a point for and against it. If people find Haskell useful for scripting, then it is a scripting language. No need to be offended. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Compiling a DSL on the shoulders of GHC

On Sun, Oct 17, 2010 at 12:12 PM, Patai Gergely patai_gerg...@fastmail.fm wrote: And it is not enough to provide just a driver function, that is called in 'main', say run :: IOArrow a b - a - IO b ? No, because I need to compile the stream processing program itself by a different tool. Not sure how this fits into what I thought you were saying. Are you trying to use Haskell to build an AST, use GHC to optimize it, and then spit it out and compile it with, say, a OCaml program that you have already written? Or is your different tool supposed to spit out Haskell and GHC compiles it into a program? Or what? What is this different tool and how does it fit in to your pipeline? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Text: find

On Sun, Oct 17, 2010 at 4:05 PM, Bryan O'Sullivan b...@serpentine.com wrote: On Sun, Oct 17, 2010 at 1:51 PM, Antoine Latter aslat...@gmail.com wrote: What would the definition of a function of the form: find :: (Text - Bool) - Text - Maybe Text look like? Can you be more specific? I assume you mean that the only sensible return values are Nothing or the entire Text for which the predicate first returns True? (In other words, that this function doesn't actually seem to have a useful return type.) Presumably find has more to do with text than: find p t = guard (p == t) (Just t) If you are searching for a... substring(?) then the value of the matching predicate could be very interesting. Eg. findName = find (all isAlpha) However, there are n^2 substrings in a string, so this function is O(P(n)n^2), where P(n) is the complexity of p. I can't say I would use such an expensive function very often -- there is usually a more specific algorithm that does what I need. Or maybe it finds prefixes? Then it should be called findPrefix probably. Oh and what if it finds more than one? Ordered by starting char? What if there multiple matches at the same starting char? So... I don't understand the specification of this function (the documentation in Data.Text is not very elucidating). Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Strict Core?

On Fri, Oct 15, 2010 at 4:21 PM, Andrew Coppin andrewcop...@btinternet.com wrote: On 15/10/2010 11:10 PM, Gregory Crosswhite wrote: Yes, I had seen this paper before and wondered the same thing at the time, but it was only just now when you brought the paper up that I realized I could ask people about it here. :-) I wonder if anybody has a list somewhere of really cool stuff that we'd love to add to GHC if only we weren't constantly snowed under with PowerPC linker glitches and obscure type system errors... ;-) I think a more appropriate description of the list would be: really cool stuff that we'd love to add to GHC if only we weren't constantly busy adding other cool stuff. GHC Team++. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Re-order type (flip map)

On Sun, Oct 10, 2010 at 4:47 PM, Ozgur Akgun ozgurak...@gmail.com wrote: On 10 October 2010 22:32, Johannes Waldmann waldm...@imn.htwk-leipzig.de wrote: Oh, and while we're at it - are there standard notations for forward function composition and application? I mean instead of h . g . f $ x I'd sometimes prefer x ? f ? g ? h but what are the ? While asking you use the same symbol for function composition, and something like inverse function application. I don't think there exists an operator ?, such that h . g . f $ x is equivalent to x ? f ? g ? h. infixl 9 ? x ? f = f x h . g . f $ x = h (g (f x)) = h (g (x ? f)) = h (x ? f ? g) = x ? f ? g ? h Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Eta-expansion destroys memoization?

On Thu, Oct 7, 2010 at 6:17 AM, Brent Yorgey byor...@seas.upenn.edu wrote: The source code seems to be easy to read, but I don't think I understand that. For me I think if I change the first line from fib = ((map fib' [0 ..]) !!) to fib x = ((map fib' [0 ..]) !!) x It should do the same thing since I think the previous version is just an abbreviation for the second one. Semantically, yes. And it's possible that ghc -O is clever enough to notice that. But at least under ghci's naive evaluation strategy, lambdas determine the lifetime of expressions. Any expression within a lambda will be re-evaluated each time the lambda is expanded. Thus: fib = (map fib' [0..] !!)-- fast fib = \x - map fib' [0..] !! x-- slow fib = let memo = map fib' [0..] in \x - memo !! x -- fast The section works because (a %^) (for some operator %^) is short for (%^) a and (%^ a) is short for flip (%^) a. Sections don't expand into lambdas. In other words, in the middle expression, there is a new map fib' [0..] for each x, whereas in the others, it is shared between invocations. Does that make sense? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Pronouncing Curry and currying

Here's how I say it (literally): http://hubrisarts.com/curry.wav On Wed, Oct 6, 2010 at 1:21 PM, Petr Pudlak d...@pudlak.name wrote: Hi all, I have a question for native English speakers: What is the correct pronunciation of the name Curry (in Haskell Curry) and the derived verb currying? I found on Wikitonary the name is (probably) of Irish orgin, so I suppose that the pronunciation may by nonstandard. Probably the best way to answer would be either a link to some voice sample or written using some standard phonetic alphabet. Thanks a lot, Petr -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJMrMwlAAoJEC5dcKNjBzhnG8UH/0E2D76OkcFwgJg4MFMEjQlI YlUoFxPurNakvcnSEtInP0uIpheDHzXqiZGnmcnq/3gwh/fapESh6pDFIxvgf7KW ikhRFlatE7dMmRVgr72qIeWD/cVF71w9FkYhDavgpMhLyzQQV4i/SyGABkHZEds6 b6VSnqWHoa1k15RxTWt30hOaqqE8+4mLQDrIBAAL9z5jBTOgeKVVq07JgeFYiioU 7wwXFM8kx+z5MsVQKKBUtRZ/+It3KRBTKW7NvhYehLn7mp/tLEIXrsJtlgqZrbHr K0rsIFeKoocih+iCm2T3lwYZI196FreVWzhFwpHAc4DJ0+86ghGLiH+lqFhjgn4= =OMQc -END PGP SIGNATURE- ___ 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] Polyvariadic functions operating with a monoid

On Sun, Oct 3, 2010 at 1:24 AM, Kevin Jardine kevinjard...@gmail.com wrote: I had a situation where I had some related types that all had toString functions. Of course in Haskell, lists all have to be composed of values of exactly the same type, so instead of passing around lists of values with these related types, I created a polyvariadic function polyToString so that I could write: (polyToString value1 value2 value3 ... valueN) which would then become a list of strings: [toString value1, toString value2, ... , toString valueN] First of all, you are not using the monoidal structure of String at all. This trick ought to work for any type whatsoever -- you're just throwing them in a list. Other than a few brackets, commas, and a repeated identifier (which you can let-bind to shorten), what benefit is it giving you? I strongly recommend against polyvariadic functions. While you get a little bit of notational convenience, you lose composability. There are pains when you try to write a function that takes a polyvariadic function as an argument, or when you try to feed the function values from a list, etc. The mechanisms to create polyvariadic functions are brittle and hacky (eg. you cannot have a polymorphic return type, as you want in this case). Since all your values are known statically, I would recommend biting the bullet and doing it the way you were doing it. [ s value1, s value2, s value3, ... ] where s x = toString x (I had to eta expand s so that I didn't hit the monomorphism restriction) When you want to be passing around heterogeneous lists, it usually works to convert them before you put them in the list, like you were doing. I finally figured out how to do this, but it was a bit harder to figure this out than I expected, and I was wondering if it might be possible to create a small utility library to help other developers do this. It seems to me that in the general case, we would be dealing with a Monoid rather than a list of strings. We could have a toMonoid function and then return polyToMonoid value1 value2 ... valueN = (toMonoid value1) `mappend` (toMonoid value2) 'mappend' ... (toMonoid valueN) So anyone who wanted to convert a bunch of values of different types to a Monoid could easily pass them around using polyToMonoid so long as they defined the appropriate toMonoid function. Basically, a generalised list. So I tried writing the following code but GHC said it had undecidable instances. Has this ever been done successfully? class Monoidable a where toMonoid :: Monoid r = a - r polyToMonoid :: (Monoidable a, Monoid r) = a - r polyToMonoid k = polyToMonoid' k mempty class PolyVariadic p where polyToMonoid' :: (Monoidable a, Monoid r) = a - r - p instance Monoid r = PolyVariadic r where polyToMonoid' k ss = (toMonoid k) `mappend` ss instance (Monoidable a, Monoid r) = PolyVariadic (a - r) where polyToMonoid' k ss = (\a - polyToMonoid' k (toMonoid a) `mappend` ss) ___ 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] Polyvariadic functions operating with a monoid

On Sun, Oct 3, 2010 at 1:26 PM, Luke Palmer lrpal...@gmail.com wrote: On Sun, Oct 3, 2010 at 1:24 AM, Kevin Jardine kevinjard...@gmail.com wrote: I had a situation where I had some related types that all had toString functions. Of course in Haskell, lists all have to be composed of values of exactly the same type, so instead of passing around lists of values with these related types, I created a polyvariadic function polyToString so that I could write: (polyToString value1 value2 value3 ... valueN) which would then become a list of strings: [toString value1, toString value2, ... , toString valueN] First of all, you are not using the monoidal structure of String at all. This trick ought to work for any type whatsoever -- you're just throwing them in a list. Oops, sorry for not reading your message more closely. You were indeed talking about the monoidal structure of list. So... nevermind about this comment. :-P Other than a few brackets, commas, and a repeated identifier (which you can let-bind to shorten), what benefit is it giving you? I strongly recommend against polyvariadic functions. While you get a little bit of notational convenience, you lose composability. There are pains when you try to write a function that takes a polyvariadic function as an argument, or when you try to feed the function values from a list, etc. The mechanisms to create polyvariadic functions are brittle and hacky (eg. you cannot have a polymorphic return type, as you want in this case). Since all your values are known statically, I would recommend biting the bullet and doing it the way you were doing it. [ s value1, s value2, s value3, ... ] where s x = toString x (I had to eta expand s so that I didn't hit the monomorphism restriction) When you want to be passing around heterogeneous lists, it usually works to convert them before you put them in the list, like you were doing. I finally figured out how to do this, but it was a bit harder to figure this out than I expected, and I was wondering if it might be possible to create a small utility library to help other developers do this. It seems to me that in the general case, we would be dealing with a Monoid rather than a list of strings. We could have a toMonoid function and then return polyToMonoid value1 value2 ... valueN = (toMonoid value1) `mappend` (toMonoid value2) 'mappend' ... (toMonoid valueN) So anyone who wanted to convert a bunch of values of different types to a Monoid could easily pass them around using polyToMonoid so long as they defined the appropriate toMonoid function. Basically, a generalised list. So I tried writing the following code but GHC said it had undecidable instances. Has this ever been done successfully? class Monoidable a where toMonoid :: Monoid r = a - r polyToMonoid :: (Monoidable a, Monoid r) = a - r polyToMonoid k = polyToMonoid' k mempty class PolyVariadic p where polyToMonoid' :: (Monoidable a, Monoid r) = a - r - p instance Monoid r = PolyVariadic r where polyToMonoid' k ss = (toMonoid k) `mappend` ss instance (Monoidable a, Monoid r) = PolyVariadic (a - r) where polyToMonoid' k ss = (\a - polyToMonoid' k (toMonoid a) `mappend` ss) ___ 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] Re: I still cannot seem to get a GUI working under Windows.

On Sat, Oct 2, 2010 at 4:32 AM, Bulat Ziganshin bulat.zigans...@gmail.com wrote: Hello Heinrich, Saturday, October 2, 2010, 1:36:48 PM, you wrote: Would you put a flattr button [1] on the wxHaskell page? This way, people like me would be able to show their appreciation by donating a this page doesn't describe how to pay and how to got the money received. if Jeremy lives in right country, i suggest to use PayPal donations system. it allows to pay by credit card and then receive money to author's credit card Because of the way flattr distributes my money (i.e. donating has 0 marginal cost to me), I am much more likely to donate using flattr than paypal. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Ultra-newbie Question

On Sun, Sep 19, 2010 at 5:01 PM, Henrique Becker henriquebecke...@gmail.com wrote: Why not? import Data.Number.Nat as N lastN :: Integral b = b - [a] - [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Wow. That is gorgeous! I think it's basically the same idea as my zipWith implementation, but it is so much clearer here. Thanks :-) Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Ultra-newbie Question

On Mon, Sep 20, 2010 at 5:11 PM, Luke Palmer lrpal...@gmail.com wrote: On Sun, Sep 19, 2010 at 5:01 PM, Henrique Becker henriquebecke...@gmail.com wrote: Why not? import Data.Number.Nat as N lastN :: Integral b = b - [a] - [a] lastN n xs = N.drop (N.length xs - n') xs where n' = N.toNat n Wow. That is gorgeous! I think it's basically the same idea as my zipWith implementation, but it is so much clearer here. Thanks :-) Er forget that zipWith comment. It is quite unlike that. But it is still beautiful and efficient. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Ultra-newbie Question

I think this is O(n) time, O(1) space (!). lastk :: Int - [a] - [a] lastk k xs = last $ zipWith const (properTails xs) (drop k xs) where properTails = tail . tails Luke On Sat, Sep 18, 2010 at 1:51 PM, Daniel Fischer daniel.is.fisc...@web.de wrote: On Saturday 18 September 2010 19:44:38, Jake McArthur wrote: On 09/18/2010 02:51 AM, Christopher Tauss wrote: I am trying to write a function that takes a list and returns the last n elements. This may just be for the sake of learning, in which case this is fine, but usually, needing to do this would be a sign that you are using lists improperly (since this is a O(n) time operation). By which he meant O(length list), not the number of elements you're asking for. Let's call the function n_lastn and, given a list [1,2,3,4,5], I would like n_lastn 3 = [3,4,5] n_lastn n = reverse . take n . reverse Which is the most elegant definition, but it's an O(length list) space operation (as are all others proposed so far). That will be a problem for long lists (consider n_lastn 10 [1 .. 10^8]). You can implement it as an O(n) [the number of elements you want] *space* operation, provided that the list is generated lazily and not referred to by anything else, but the code is decidedly less nice: The first idea would be to keep a window of n elements and move it to the end of the list: n_lastn n xs = case splitAt n xs of (ys,[]) - ys -- the list contains at most n elements, yay (ys,zs) - loop ys zs where loop window [] = window loop window (v:vs) = loop (tail window ++ [v]) vs The space behaviour is now fine (if compiled with optimisations), but unfortunately, the time complexity has become O(n*length list) because the (++)-calls are left-nested: Suppose n = 4, loop (1:2:3:4:[]) [5 .. end] ~ loop ((2:3:4:[]) ++ [5]) [6 .. end] ~ loop (2:((3:4:[]) ++ [5])) [6 .. end] ~ loop (((3:4:[]) ++ [5]) ++ [6]) [7 .. end] The strictness analyser has been smart enough to transform the call to tail into a strict pattern match on window, as if we'd written loop (_:twindow) (v:vs) = loop (twindow ++ [v]) vs so the first few tails go fast, but later, we have to go through more layers to get at the head of the window to discard it ~ loop ((3:((4:[]) ++ [5])) ++ [6]) [7 .. end] ~ loop (3:(((4:[]) ++ [5]) ++ [6])) [7 .. end] -- finally! ~ loop 4:[]) ++ [5]) ++ [6]) ++ [7]) [8 .. end] -- bubble the 4 through four layers of parentheses: ~ loop(((4:([] ++ [5])) ++ [6]) ++ [7]) [8 .. end] ~ loop ((4:(([] ++ [5]) ++ [6])) ++ [7]) [8 .. end] ~ loop (4:((([] ++ [5]) ++ [6]) ++ [7])) [8 .. end] ~ loop [] ++ [5]) ++ [6]) ++ [7]) ++ [8]) [9 .. end] -- phew -- form now on, it's uniform, on each step we have to match an expression [] ++ [a]) ++ [b]) ++ [c]) ++ [d]) against (_:rest) 1. check whether ((([] ++ [a]) ++ [b]) ++ [c]) is empty, for that, 2. check whether (([] ++ [a]) ++ [b]) is empty, for that, 3. check whether ([] ++ [a]) is empty, for that, 4. check whether [] is empty, it is, hence [] ++ [a] = [a], 5. check whether [a] is empty, it's not, it's (a:[]), hence 6. (...) ++ [b] = a:([] ++ [b]), so 2's not empty, and 7. (...) ++ [c] = a:(([] ++ [b]) ++ [c]), so 1's not empty and 8. (...) ++ [d] = a:((([] ++ [b]) ++ [c]) ++ [d]) 9. at last, a can be dropped and we get to loop [] ++ [b]) ++ [c]) ++ [d]) ++ [e]) remainingList Blech! Appending to the end of a list is bad if it leads to left-nested parentheses (it's okay if the parentheses are right-nested). So we might be tempted to keep the window reversed and cons each element to the front, dropping the last. No good, removing an element from the end is O(length window) too. One possibility to fix it is to use a 'list-like' type with O(1) appending at the end and dropping from the front. Data.Sequence is such a type, import qualified Data.Sequence as Seq import Data.Foldable (toList) import Data.Sequence (ViewL(..), (|)) n_lastn' :: Int - [a] - [a] n_lastn' k _ | k = 0 = [] n_lastn' k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go (Seq.fromList ys) zs where go acc [] = toList acc go acc (v:vs) = case Seq.viewl acc of _ : keep - go (keep | v) vs _ - error teh impossible jus hapnd fixes space and time behaviour. But the constant factors for Sequence are larger than those for lists, so we can beat it with lists: n_lastn :: Int - [a] - [a] n_lastn k _ | k = 0 = [] n_lastn k xs = case splitAt k xs of (ys,[]) - ys (ys,zs) - go k (reverse ys) zs where m = k-1 go _ acc [] = reverse $ take k acc go 0 acc (v:vs) = case splitAt m acc of (keep,release) - release `seq` go k (v:keep) vs go h acc (v:vs) = go (h-1) (v:acc) vs Every k steps, we perform the O(k) operation of removing the last (k+1) elements from a (2k)-element list,

### Re: [Haskell-cafe] Reachable variables exercise

I am not totally sure if I understand your proposal correctly, but if I do, then it has a flaw. Consider: class Boolable a where boolify :: a - Bool class O a where o :: a main = print $ boolify o It seems like under your proposal this should not be a type error. But if that is so, then what is its output? Luke On Thu, Sep 16, 2010 at 7:31 AM, Carlos Camarao carlos.cama...@gmail.com wrote: Hi. Consider for example an expression e0 like: fst (True,e) where e is any expression. e0 should have type Bool IMHO irrespectively of the type of e. In Haskell this is the case if e's type is monomorphic, or polymorphic, or constrained and there is a default in the current module that removes the constraints. However, e0 is not type-correct if e has a constrained type and the constraints are not subject to defaulting. For example: class O a where o::a main = print $ fst(True,o) generates a type error; in GHC: Ambiguous type variable `a' in the constraint: `O a' arising from a use of `o' at ... Probable fix: add a type signature that fixes these type variable(s) A solution (that avoids type signatures) can be given as follows. The type of f e, for f of type, say, K=t'-t and e of type K'= t' should be: K +_t K' = t (not K U K' = t) where K +_t K' denotes the constraint-set obtained by adding from K' only constraints with type variables reachable from t. (A type variable is reachable if it appears in the same constraint as either a type variable free in the type, or another reachable type variable.) Comments? Does that need and deserve a proposal? Cheers, Carlos ___ 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] record update

On Tue, Sep 14, 2010 at 1:31 PM, Jonathan Geddes geddes.jonat...@gmail.com wrote: With these extensions, couldn't I write the following? someUpdate :: MyRecord - MyRecord someUpdate myRecord@(MyRecord{..}) = let { field1 = f field1 , field2 = g field2 , field3 = h filed3 } in myRecord{..} No, those are recursive let bindings! If f = (1:), then field1 = [1,1,1,1...] As Conrad suggests, use: someUpdate myRecord@(MyRecord{..}) = myRecord { field1 = f field1 , field2 = f field2 , field3 = f field3 } The reason this works is that field1 in field1 = is not a real scoped variable, but rather an identifier for a field in the record. It's all somewhat subtle... Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Statically tracking validity - suggestions?

I have a description of the design pattern you need, appropriately named: http://lukepalmer.wordpress.com/2009/03/24/certificate-design-pattern/ On Tue, Aug 31, 2010 at 12:24 AM, strejon strej...@yahoo.com wrote: Hello. I'm using Haskell to write a specification for some software. The software uses certificates (standard X.509 certificates) and stores user name information in the Subject's CommonName field. The X.509 standard doesn't actually require the presence of a CommonName field so the contents of the Subject section (with the rest of the fields omitted) are just represented by a Maybe User_Name. import Data.List (find, concat) import Data.Maybe (fromJust, isJust) type User_Name = String type Public_Key = Integer data Subject_Name = Subject_Name (Maybe User_Name) deriving (Show, Eq) data Certificate = Certificate { certificate_subject :: Subject_Name, certificate_key :: Public_Key, certificate_issuer :: String, certificate_serial :: Integer } deriving (Show, Eq) This is all well and good, but the problem is that the validity of certificates isn't tracked statically and I have to use the following as guards on all functions that only expect valid certificates (and inevitably handle cases that I know can't actually happen but have to be handled in pattern matching and the like, bloating the specification): user_name :: Subject_Name - Maybe User_Name user_name (Subject_Name name) = name is_valid :: Certificate - Bool is_valid = isJust . user_name . certificate_subject I'm aware of phantom types and the like, but I've been unable to work out how to use them (or another type system extension) to properly track validity on the type level. I'd want something like: validate :: Certificate Possibly_Valid - Maybe (Certificate Valid) With later functions only accepting values of type Certificate Valid. Is there a simple way to do this? -- View this message in context: http://old.nabble.com/Statically-tracking-%22validity%22---suggestions--tp29579872p29579872.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.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] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?

On Mon, Aug 23, 2010 at 1:06 AM, Heinrich Apfelmus apfel...@quantentunnel.de wrote: Conal Elliott wrote: For anyone interested in iteratees (etc) and not yet on the iteratees mailing list. I'm asking about what iteratees *mean* (denote), independent of the various implementations. My original note (also at the end below): In my world view, iteratees are just a monad M with a single operation symbol :: M Char that reads the next symbol from an input stream. So perhaps this could be a reasonable semantics? Iteratee a = [Char] - Maybe (a, [Char]) = MaybeT (State [Char]) a symbol [] = Nothing symbol (c:cs) = Just (c, cs) I'm not experienced with iteratees. Does this miss something? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Simple Sudoku solver using Control.Monad.Logic

On Sun, Aug 22, 2010 at 1:18 PM, Daniel Fischer daniel.is.fisc...@web.de wrote: On Sunday 22 August 2010 20:12:16, Vladimir Matveev wrote: I think the problem is with terribly inefficient data representation. Worse, it's a terribly inefficient algorithm. The constraints are applied too late, so a huge number of partial boards are created only to be pruned afterwards. Since the ratio between obviously invalid rows and potentially valid rows is large, the constraints should be applied already during the construction of candidate rows to avoid obviously dead branches. I've written a sudoku solver myself, and IIRC I used lists. It always gave an answer within a second. So I believe Daniel has correctly identified the problem -- you need to prune earlier. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] lazy skip list?

On Thu, Aug 19, 2010 at 9:57 PM, Felipe Lessa felipe.le...@gmail.com wrote: However, I haven't thought about how operations such as 'cons' and 'tail' would be implemented =). OP just asked about indexing ;-). Well if all you need is indexing, then an integer trie does it, right? http://hackage.haskell.org/package/data-inttrie Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Can we come out of a monad?

On Mon, Aug 9, 2010 at 1:19 PM, John Lato jwl...@gmail.com wrote: I don't find purify2 particularly helpful because I almost never want to break out of any arbitrary monad; I want to be able to break out of a specific monad without knowing which monad it is, that is: purify3 :: Monad m = m a - a purify3 = undefined --the only possible definition... However, I just realized that something else is almost as good: evalCont :: Cont r a - r evalCont k = runCont k id Except, of course, you want the signature evalCont :: Cont r a - a Which is not possible. But I am not sure where all this discussion is coming from, Maybe and (r -) cannot be broken out of. Isn't that example enough? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Laziness question

On Sun, Aug 1, 2010 at 2:53 AM, Stefan Holdermans ste...@vectorfabrics.com wrote: Nicolas, I would deeply in favor of renaming seq to unsafeSeq, and introduce a type class to reintroduce seq in a disciplined way. There is a well-documented [1] trade-off here: Often, calls to seq are introduced late in a developing cycle; typically after you have discovered a space leak and figured out how to resolve it. Then you introduce a call to seq somewhere deep in a call chain. If seq were a class method, you would know have to work your way upward in the call chain to update all type signatures you had written there. Clearly, this is quite tedious. And then, almost just as often, you find out that actually you did not quite figure out how to resolve the space leak, because it's still there. So, you remove your freshly introduced call to seq and, indeed, work your way to the call chain again to remove all now superfluous class constraints from the type signatures. (By the way, this is typically the sort of task, IDEs with refactoring support excel at, but these are unfortunately not ubiquitous for Haskell yet.) That's a reasonable concern. I suppose that would be the reason for keeping unsafeSeq around if we do typeclassify seq. More importantly, the type-class approach is flawed [2]. It assumes that all seq-related constraints can be read off from type variables, which is in fact not the case. Could you provide an example (or a specific example or explanation in the paper) of what you mean by this? Luke Cheers, Stefan [1] Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler. A history of Haskell: Being lazy with class. In Barbara G. Ryder and Brent Hailpern, editors, Proceedings of the Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III), San Diego, California, USA, 9–10 June 2007, pages 1–55. ACM Press, 2007. http://doi.acm.org/10.1145/1238844.1238856 [2] Daniel Seidel and Janis Voigtländer. Taming selective strictness. In Stefan Fischer, Erik Maehle, and Rüdiger Reischuk, editors, INFORMATIK 2009 – Im Focus das Leben, Beiträge der 39. Jahrestagung der Gesellschaft für Informatik e.V. (GI), 28. September – 2. Oktober, in Lübeck, volume 154 of Lecture Notes in Informatics, pages 2916–2930. GI, 2009.___ 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] OpenGL Speed!

Yep, no surprise there. I would suggest using bitmap[1] to construct your bitmap, and bitmap-opengl to put it into an OpenGL texture and draw it on a textured quad. I think OpenGL is actually an OK choice for this application, because it is the most portable graphics method we have available. If you are trying to redraw in realtime, eg. 30 FPS or so, I don't think you're going to be able to. There is just not enough GPU bandwidth (and probably not enough CPU) for that (unless you write it in a pixel shader, which IIRC haskell has some neat tools for, but I don't remember). If this is the case, see if you can boil down what you have into something that doesn't require so much data, e.g. polygons. [1] http://hackage.haskell.org/package/bitmap [2] http://hackage.haskell.org/package/bitmap-opengl On Thu, Jul 29, 2010 at 3:57 AM, Eitan Goldshtrom thesource...@gmail.com wrote: I'm having an unusual problem with OpenGL. To be honest I probably shouldn't be using OpenGL for this, as I'm just doing 2D and only drawing Points, but I don't know about any other display packages, so I'm making due. If this is a problem because of OpenGL however, then I'll have to learn another package. The problem is speed. I have a list of points representing the color of 800x600 pixels. All I'm trying to do is display the pixels on the screen. I use the following: renderPrimitive Points $ mapM_ display list flush where display [] = return () display ((x,y,i):n) = do color $ Color3 i i i vertex $ Vertex2 x y display n But, for some reason this takes FOREVER. I don't know how to use debugging hooks yet without an IDE -- and I don't use an IDE -- but I used a cleverly placed putStrLn to see that it was actually working, just really really slowly. Is there a solution to this speed problem or should I use a package that's more suited to 2D applications like this? Also, if I should use another package, are there any suggestions for which to use? Thanks for any help. -Eitan ___ 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] Memoization in Haskell?

On Thu, Jul 8, 2010 at 4:23 PM, Daniel Fischer daniel.is.fisc...@web.de wrote: On Friday 09 July 2010 00:10:24, Daniel Fischer wrote: You can also use a library (e.g. http://hackage.haskell.org/package/data- memocombinators) to do the memoisation for you. Well, actualy, I think http://hackage.haskell.org/package/MemoTrie would be the better choice for the moment, data-memocombinators doesn't seem to offer the functionality we need out of the box. I'm interested to hear what functionality MemoTrie has that data-memocombinators does not. I wrote the latter in hopes that it would be strictly more powerful*. Luke * Actually MemoTrie wasn't around when I wrote that, but I meant the combinatory technique should be strictly more powerful than a typeclass technique. And data-memocombinators has many primitives, so I'm still curious. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Finding zipper for custom tree

On Thu, Jul 1, 2010 at 1:54 PM, Sergey Mironov ier...@gmail.com wrote: Hello list! I am trying to understand zipper concept using papers like [1] and [2]. Though main idea looks clear, I still have a problem in applying it for custom data types. Please help me with deriving Zipper-type from data DTree a = P | D [(a, DTree)] Looking in [1] ('Zippers via Differentiation' chapter) I tried to do the following: 1. Find a DTreeF type which is a pattern functor ([2], chapter 2.1) of my DTree 2. Write DTreeF in 'algebraic' form (using '+' and '*') 3. Find DTreeF' - derivative of DTreeF 4. Define my zipper type using list of DTreeF' Step 1 likely ends with data DTreeF a x = P | D [(a,x)] [2] says that using this pattern functor one could build a fixed-point version of DTree: data Fix f = In {out :: (f (Fix f))} data DTreeFP = Fix DTreeF but seems that I have nothing to do with it right now. Step 2 is my main question: In [1] authors did it for binary tree: data Tree a = Leaf a | Bin (Tree a) (Tree a) data TreeF a x = Leaf a | Bin x x and thus TreeF = a + x * x TreeF' = x + x My DTree has inner list of tuples. How should I rewrite it in terms of '+' and '*' ? I would just use List. IIRC the derivative of list is: data DList a = DLIst [a] [a] Understood as the elements before the focused one and those after it. Unfortunately I can't remember how that is derived, and my own experiments failed to come up with anything similar. That may indicate that the rest of this message is nonsense. data DTree a = P | D [(a, DTree a)] Can be written algebraically as: DTree a = 1 + List (a * DTree a) DTree a = Mu f. 1 + List (a * f) Differentiating: DDTree a = Mu f. DList (a * f) * a DDTree a = DList (a * DTree a) * a To understand this intuitively, DDTree a is the context in which a DTree can appear within itself. So that is: The (a * DTree a)s that appeared before and after the current list element, together with the a that was paired with the current element. At least that is how I understand it. I admit there was some handwaving going on in the details. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] whine and solution about programmers not respecting documentations

On Mon, Jun 28, 2010 at 1:44 PM, Albert Y.C.Lai tre...@vex.net wrote: Why should anyone expect deleteBy (=) 5 [0..10] to accomplish anything meaningful, if he/she respects the written docs? I proposed the following solution: http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/ Today someone on #haskell expected it to accomplish something meaningful, even something mind-reading. The said person has been around for more than a year, not eligible for the newbie excuse. The said person is just the tip of an iceberg. The doc of deleteBy states: The deleteBy function behaves like delete, but takes a user-supplied equality predicate. A precondition is that the user-supplied predicate is an equality predicate. (=) is not an equality predicate, be it in the layperson sense of it isn't analogous to (==) or the mathematical sense of it isn't an equivalence relation. If you respect the precondition or the authors of the doc, you should just never use deleteBy (=) 5 [0..10], much less expect any meaningful result. I propose this solution: For each of deleteBy, groupBy, unionBy... we can usually conceive at least two implementations, behaving pretty much the same (answer, speed, space) when given an equivalence relation (modulo some rare concern when the equivalence relation has assymetric strictness properties), but behaving different when not, and their code sizes are pretty much the same. With more imagination and allowing some code bloat, perhaps we can conceieve more implementations. But two suffices, really. I propose that at each minor version of base, someone picks an implementation randomly. Here is a more radical, less labour-intensive solution, if you don't mind a judicious, correctness-preserving use of unsafePerformIO: at the first invocation of the process lifetime, pick an implementation randomly. The result frustrates people who disrespect the docs. My purpose is exactly that. The goal is to give people an incentive to not disrepect the docs. (If you think this is a nasty stick, not carrot incentive, on first thought I would agree. On second thought, it is not adding a stick, it is just removing a carrot. Programmer's carrot means his/her code works consistently. When deleteBy (=) works consistently, you are giving out undeserved free carrots --- incentive to write more wrong code. I am proposing to remove undeserved free carrots.) ___ 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] The Arrow class (was: Vague: Assembly line process)

On Fri, Jun 18, 2010 at 5:57 PM, Ryan Ingram ryani.s...@gmail.com wrote: Related to this, I really would like to be able to use arrow notation without arr; I was looking into writing a circuit optimizer that modified my arrow-like circuit structure, but since it's impossible to look inside arr, I ran into a brick wall. Has anyone done any analysis of what operations arrow notation actually requires so that they can be made methods of some typeclass, instead of defining everything in terms of arr? Well, there's DeepArrow. I'm not sure if it's minimal or anything, but IIRC that was its purpose. It seems to me the trickiness comes when you have patterns and complex expressions in your arrow notation, that is, you write (a,b) - some_arrow - (c,d) returnA - a instead of x - some_arrow - y returnA - x But I expect to be able to do the latter without requiring arr, and that does not seem to happen. -- ryan On Wed, Jun 16, 2010 at 11:18 AM, Edward Kmett ekm...@gmail.com wrote: On Wed, Jun 16, 2010 at 6:55 AM, Tillmann Rendel ren...@mathematik.uni-marburg.de wrote: Bas van Dijk wrote: data Iso (⇝) a b = Iso { ab ∷ a ⇝ b , ba ∷ b ⇝ a } type IsoFunc = Iso (→) instance Category (⇝) ⇒ Category (Iso (⇝)) where id = Iso id id Iso bc cb . Iso ab ba = Iso (bc . ab) (ba . cb) An 'Iso (⇝)' also _almost_ forms an Arrow (if (⇝) forms an Arrow): instance Arrow (⇝) ⇒ Arrow (Iso (⇝)) where arr f = Iso (arr f) undefined first (Iso ab ba) = Iso (first ab) (first ba) second (Iso ab ba) = Iso (second ab) (second ba) Iso ab ba *** Iso cd dc = Iso (ab *** cd) (ba *** dc) Iso ab ba Iso ac ca = Iso (ab ac) (ba . arr fst) -- or: (ca . arr snd) But note the unfortunate 'undefined' in the definition of 'arr'. This comes up every couple of years, I think the first attempt at formulating Iso wrongly as an arrow was in the There and Back Again paper. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.7278 It comes up now and again, because the types seem to _almost_ fit. =) The reason is that an arrow is a closed pre-Cartesian category with a little bit of extra structure. Isomorphisms and embedding-projection pairs are a bit too constrained to meet even the requirements of a pre-Cartesian category, however. This seems to suggest that all the methods besides 'arr' need to move to a separate type class. You may be interesting in following the construction of a more formal set of categories that build up the functionality of arrow incrementally in category-extras. An arrow can be viewed as a closed pre-cartesian category with an embedding of Hask. Iso on the other hand is much weaker. The category is isomorphisms, or slightly weaker, the category of embedding-projection pairs doesn't have all the properties you might expect at first glance. You an define it as a Symmetric Monoidal category over (,) using a Bifunctor for (,) over Iso: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor.html the assocative laws from: http://hackage.haskell.org/packages/archive/category-extras/0.52.1/doc/html/Control-Category-Associative.html The definitions of Braided and Symmetric from: http://hackage.haskell.org/packages/archive/category-extras/0.52.1/doc/html/Control-Category-Braided.html and the Monoidal class from: http://hackage.haskell.org/packages/archive/category-extras/0.52.1/doc/html/Control-Category-Monoidal.html This gives you a weak product-like construction. But as you noted, fst and snd cannot be defined, so you cannot define Cartesian http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Category-Cartesian.html let alone a CCC http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Category-Cartesian-Closed.html or Arrow. =( Wouldn't it be better to have a definition like this: class Category (~) = Products (~) where (***) :: (a ~ b) - (c ~ d) - ((a, c) ~ (b, d)) () :: (a ~ b) - (a ~ c) - (a ~ (b, c)) fst :: (a, b) ~ a snd :: (a, b) ~ b You've stumbled across the concept of a Cartesian category (or at least, technically 'pre-Cartesian', though the type of product also needs to be a parameter or the dual of a category with sums won't be a category with products. http://hackage.haskell.org/packages/archive/category-extras/0.52.1/doc/html/Control-Category-Cartesian.html Or even like this: class Category (~) = Products (~) where type Product a b (***) :: (a ~ b) - (c ~ d) - (Product a c ~ Product b d) () :: (a ~ b) - (a ~ c) - (a ~ Product b c) fst :: Product a b ~ a snd :: Product a b ~ b This was the formulation I had originally used in category-extras for categories. I swapped to MPTCs due to implementation defects in type families at the time, and intend to swap

### Re: [Haskell-cafe] How to browse code written by others

On Mon, Jun 14, 2010 at 2:02 AM, Jean-Marie Gaillourdet j...@gaillourdet.net wrote: Hello, On 13.06.2010, at 22:32, Martin Drautzburg wrote: I need your advice about how to browse code which was written by someone else (Paul Hudak's Euterpea, to be precise, apx. 1 LOC). I had set some hopes on leksah, and it indeed shows me the interfaces, but I have not yet convinced it to show me more than that. I ran haddock over the sources, and again I could not see more that just signatures. I would be very happy with something like a Smalltalk browser. Something that would let me zoom down to the source code, but with search and hyperlink capabilities (senders and implementers in Smalltalk). Anyways, how do you guys do it, i.e. how to you dive into non-trivial foreign code? I use the following tools: * haddock generated docs with hyperlinked sources * MacVim (or just vim) with Claus Reinke's haskellmode-vim, see: http://projects.haskell.org/haskellmode-vim/index.html Have a look at the screencasts to see documentation lookup, and code navigation: http://projects.haskell.org/haskellmode-vim/screencasts.html Make sure you know how to use tags inside of vim. ghci is able to generate the tagsfiles for you. This allows you to jump to definitions of identifiers. If you go this route, I will shamelessly promote hothasktags instead of ghci. It generates proper tags for qualified imports. * SourceGraph, it generates an HTML report of a cabal projekt or of any source tree. IMHO, great to get the overall picture. Regards, Jean-Marie ___ 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] Vague: Assembly line process

So hang on, what is the problem? You have described something like a vague model, but what information are you trying to get? Say, perhaps, a set of possible output lists from a given input list? Luke On Mon, Jun 14, 2010 at 11:16 AM, Martin Drautzburg martin.drautzb...@web.de wrote: Hello all, this is a problem which has haunted me for some time. If this is simply hillarious, please tell me so. Or it may be some well known unsolvable problem... An assembly process takes inputs and produces outputs. I could say a Process is a function canProduce :: [Input]-[Output]-Bool which tells me if the outputs can be produced from the inputs There may be a similar function which tells me if the inputs are completely consumed to procude the output. The inputs do not determine the exact outputs. Think of a Process which combines a List of Ints into pairs, such that the input ints are consumed and each input Int occurs in only one position in the output. There are many ways to do this. Still for any set of input Ints and output pairs I could decide if the output can be produced from the input. Likewise the Input is not determined by the output. There may be lots of choices from what I could build my output (buy from different vendors). When I know more about the inputs and outputs my choices get more and more limited. I would like to to pass inputs and/or outputs to something and I would like to get a something which is more restricted, but still essentially a thing which tells me if the outputs can be produced from the inputs. I just cannot find a way to even THINK about this problem in a reasonable general way. -- Martin ___ 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] Re: How to Show an Operation?

On Thu, Jun 10, 2010 at 2:10 PM, Maciej Piechotka uzytkown...@gmail.com wrote: data Named a = Named String a instance Functor Named where f `fmap` (Named s v) = Named s (f v) instance Applicative Named where pure x = Named x (Named s f) * (Named t v) = Named (s ++ ( ++ t ++ )) (f v) This is not technically a legal applicative instance, because it is not associative. This can be seen when you try to clean up the usage as we have been discussing: g . f = liftA2 (.) g f f = Named f (+1) g = Named g (*2) h = Named h (^3) ghci f * (g * (h * namedPure 42)) f(g(h(42))) ghci (f . g . h) * namedPure 42 f(g)(h)(42) The Applicative laws are supposed to guarantee that this refactor is legal. Of course, the latter answer is nonsense. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Thread scheduling

On Thu, Jun 10, 2010 at 11:50 AM, Andrew Coppin andrewcop...@btinternet.com wrote: Control.Concurrent provides the threadDelay function, which allows you to make the current thread sleep until T=now+X. However, I can't find any way of making the current thread sleep until T=X. In other words, I want to specify an absolute wakeup time, not a relative one. Modulo a small epsilon between the two actions, can't you just get the current time and subtract it from the target time? threadDelay is allowed to delay for too long anyway, so doing it this way does not lose you any correctness. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Thread scheduling

Say, using System.Time.getClockTime. Luke On Thu, Jun 10, 2010 at 11:31 PM, Luke Palmer lrpal...@gmail.com wrote: On Thu, Jun 10, 2010 at 11:50 AM, Andrew Coppin andrewcop...@btinternet.com wrote: Control.Concurrent provides the threadDelay function, which allows you to make the current thread sleep until T=now+X. However, I can't find any way of making the current thread sleep until T=X. In other words, I want to specify an absolute wakeup time, not a relative one. Modulo a small epsilon between the two actions, can't you just get the current time and subtract it from the target time? threadDelay is allowed to delay for too long anyway, so doing it this way does not lose you any correctness. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: How to Show an Operation?

On Thu, Jun 10, 2010 at 10:43 PM, Brandon S. Allbery KF8NH allb...@ece.cmu.edu wrote: On Jun 10, 2010, at 17:38 , Martin Drautzburg wrote: instance Applicative Named where pure x = Named x (Named s f) * (Named t v) = Named (s ++ ( ++ t ++ )) (f v) Applicative. Need to study that The above is just the Functor, rephrased in Applicative style. * is exactly fmap. Likewise, Monad has a function liftM which is exactly fmap. (For historical reasons, these are not related the way they should be: all Monads should be Applicatives, all Applicatives should be Functors, and all Functors should be instances of an even more primitive class Pointed.) (*) :: Applicative f = f (a - b) - f a - f b ($) :: Functor f = (a - b) - f a - f b ($) is fmap, not (*). (*) is available for monads as Control.Monad.ap. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] How to Show an Operation?

On Wed, Jun 9, 2010 at 12:33 PM, Martin Drautzburg martin.drautzb...@web.de wrote: So far so good. However my Named things are all functions and I don't see I ever want to map over any of them. But what I'd like to do is use them like ordinary functions as in: f::Named (Int-Int) f x Is there a way to do this, other than writing apply::Named Int -Int apply n x = (val_of n) x What's wrong with that? (Other than the type signature, but I get what you mean). The proper type signature is apply :: Named (Int - Int) - Int - Int. You don't need the parentheses: apply n x = val_of n x Or just: apply = val_of I frequently suggest the following to new Haskellers: don't worry so much about notation. Sometimes programmers get a picture in their heads about how the code *should* look, and then they go through all manner of ugly contortions to make the notation right. I suggest that you will encounter much less pain if you accept Haskell's straightforward notation, and focus on the meaning rather than the syntax of your program. So, to summarize: if you have something that isn't a function and you want to use it like a function, convert it to a function (using another function :-P). That's all. No syntax magic, just say what you're doing. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Proof question -- (==) over Bool

2010/5/21 R J rj248...@hotmail.com: I'm trying to prove that (==) is reflexive, symmetric, and transitive over the Bools, given this definition: (==) :: Bool - Bool - Bool x == y = (x y) || (not x not y) My question is: are the proofs below for reflexivity and symmetricity rigorous, and what is the proof of transitivity, which eludes me? Thanks. Theorem (reflexivity): For all x `elem` Bool, x == x. Proof: x == x = {definition of ==} (x x) || (not x not x) = {logic (law of the excluded middle)} True This one depends on what you mean by rigorous. But you would have to have lemmas showing that and || correspond to the predicate logic notions. I would do this by cases: x = True: (True True) || (not True not True) ... True || False True x = False (False False) || (not False not False) ... False || True True Theorem (symmetricity): For all x, y `elem` Bool, if x == y, then y == x. Proof: x == y = {definition of ==} (x y) || (not x not y) = {lemma: () is commutative} (y x) || (not x not y) = {lemma: () is commutative} (y x) || (not y not x) = {definition of ==} y == x Yes, given the lemmas about and ||, this is rigorous. You can prove those lemmas by case analysis. Theorem (transitivity): For all x, y, z `elem` Bool, if x == y, and y == z, then x == z. Proof: ? My first hunch here is to try the following lemma: Lemma: if (x == y) = True if and only if x = y. where == is the version you defined, and = is regular equality from logic, if you are allowed to rely on that. I would prove this by cases. At this point, you can convert transitivity of == to transitivity of =, which is assumed by the axioms. You could do the same for the other proofs you asked about instead of brute-forcing them. If you aren't allowed such magic, then I guess you could do all 8 cases of x, y, and z (i.e. proof by truth table). Somebody else might have a cleverer idea. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] ANN: has-0.4 Entity based records

On Tue, May 4, 2010 at 10:18 AM, HASHIMOTO, Yusaku nonow...@gmail.com wrote: Hello, I'm pleased to announce the release of my new library, named has, written to aim to ease pain at inconvinience of Haskell's build-in records. Hmm, nice work, looks interesting. With the has, You can reuse accessors over records to write generic function, combine records with another. Repository is at GitHub: http://github.com/nonowarn/has Uploaded on Hackage: http://hackage.haskell.org/package/has So you can install this by cabal install has You can use the has in three steps (without counting installation). 1. Write {-# OPTIONS_GHC -fglasgow-exts #-} top of your code, This is going out of style. It would be nice to know specifically what LANGUAGE extensions are necessary. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Learning about Programming Languages (specifically Haskell)

On Mon, May 3, 2010 at 9:17 AM, Kyle Murphy orc...@gmail.com wrote: Reasons to learn Haskell include: Lazy evaluation can make some kinds of algorithms possible to implement that aren't possible to implement in other languages (without modification to the algorithm). One could say the reverse as well. I would say that laziness allows many more *compositions* of algorithms. Many more objects can be described from simple building blocks (combinators). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Strict type system allows for a maximum number of programming errors to be caught at compile time.

On Mon, May 3, 2010 at 9:34 AM, Casey Hawthorne cas...@istar.ca wrote: Strict type system allows for a maximum number of programming errors to be caught at compile time. I keep hearing this statement but others would argue that programming errors caught at compile time only form a minor subset of all errors caught. So, in functional programming languages with a strict type system, e.g. Haskell, do typing errors from a larger subset of all programming errors. Absolutely! Haskell developers trade debugging time for time arguing with the compiler about the correctness of their code. I'll give this meaningless anecdotal statistic: Compiler says my code is right = My code is actually right -- 60% Compiler says my code is wrong = My code is actually wrong -- 95% Haskell has a particular reputation for the former. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Strict type system allows for a maximum number of programming errors to be caught at compile time.

On Mon, May 3, 2010 at 11:07 AM, Kyle Murphy orc...@gmail.com wrote: The problem with dynamic typing is that it has a much higher chance of having a subtle error creep into your code that can go undetected for a long period of time. A strong type system forces the code to fail early where it's easier to track down and fix the problem, rather than trying to perform debugging on the fly in a production system. This has an added advantage for compiled languages in that for many non-trivial applications the time to build and deploy a new instance of the program, even in the development environment is often substantial, and the more trivial errors are discovered at compile time, the less time is wasted on builds. For small code bases the time spent tracking down a error at runtime might be less than the time spent making your code conform to strict type requirements, but for larger code bases the amount of time necessary to track down such errors greatly out weighs the amount of time needed to make your code well typed. To look at the flip side of your statistics: Compiler says my code is right = My code is actually wrong -- 40% Compiler says my code is wrong = My code is actually right -- 5% I'd argue this is provably wrong, as correct code by definition would compile. Here is a contrived example of what I am referring to: prefac f 0 = 1 prefac f n = n * f (n-1) fac = (\x - x x) (\x - prefac (x x)) If this code were allowed to compile (say by inserting unsafeCoerce anywhere you like), it would correctly implement a factorial function. It is precisely these cases behind the dynamically typed languages' advocacy: my code is right but I can't (or it is too much work to) convince the compiler of that fact. It is a pretty bold statement to say that these do not occur. The fact that it doesn't is proof enough that there's a problem with it even if that problem is simply that the types you're using aren't exactly correct. Further, I'd argue that in the first instance with a non-strict type system, the instance of wrong code that compiles would be higher. The only argument to support non-strict typing would be if you could show that it takes less time to track down runtime bugs than it does to fix compile time type errors, and any such claim I'd be highly skeptical of. Clearly. But many people believe in this methodology, and use test suites and code coverage instead of types. Indeed, such practices are essentially empirical type checking, and they afford the advantage that their verification is much more expressive (however less reliable) than our static type system, because they may use arbitrary code to express their predicates. What I seem to be getting at is this plane of type systems: Constrained - Expressive Unreliable | (C) |(test suites) | (C++). |. | (Java/C#)(Scala) . |. |. | (Haskell). | | (Agda) Reliable Where by Constrained/Expressive I mean the ability for the system to express properties *about the code* (so C++'s type system being turing complete is irrelevant). By Unreliable/Reliable I mean, given popular engineering practice in that language, the chance that if it passes the checks then it works as intended. For all the languages, I mean their compilers. Test suites extend down the right-hand side, depending on how rigorous you are about testing, but they never get as far down as Agda. :-) Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Strict type system allows for a maximum number of programming errors to be caught at compile time.

On Mon, May 3, 2010 at 10:13 PM, Ivan Miljenovic ivan.miljeno...@gmail.com wrote: On 4 May 2010 13:30, Luke Palmer lrpal...@gmail.com wrote: Here is a contrived example of what I am referring to: prefac f 0 = 1 prefac f n = n * f (n-1) fac = (\x - x x) (\x - prefac (x x)) I can't work out how this works (or should work rather); is it meant to be using church numerals or something (assuming that they have been made an instance of Num so that - and * work)? No they're just integers. fac is a beta expansion of fix prefac. Obseve the magic: (\x - x x) (\x - prefac (x x)) 2 (\x - prefac (x x)) (\x - prefac (x x)) 2 prefac ((\x - prefac (x x)) (\x - prefac (x x))) 2 2 * ((\x - prefac (x x)) (\x - prefac (x x)) (2-1) 2 * prefac ((\x - prefac (x x)) (\x - prefac (x x))) (2-1) 2 * prefac ((\x - prefac (x x)) (\x - prefac (x x))) 1 2 * (1 * ((\x - prefac (x x)) (\x - prefac (x x))) (1-1)) 2 * (1 * prefac ((\x - prefac (x x)) (\x - prefac (x x))) (1-1)) 2 * (1 * prefac ((\x - prefac (x x)) (\x - prefac (x x))) 0) 2 * (1 * 1) 2 Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] singleton types

2010/4/25 Günther Schmidt gue.schm...@web.de: Hello, HaskellDB makes extensive use of Singleton Types, both in its original version and the more recent one where it's using HList instead of the legacy implementation. I wonder if it is possible, not considering feasibility for the moment, to implement HaskellDB *without* using Singleton Types. Would you please define singleton type? Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] I need help getting started

On Sat, Apr 24, 2010 at 10:34 PM, mitch...@kaplan2.com wrote: Hi, I’m just starting to learn, or trying to learn Haskell. I want to write a function to tell me if a number’s prime. This is what I’ve got: f x n y = if n=y then True else if gcd x n == 1 then f x (n+1) y else False primeQ x = f x 2 y where y = floor(sqrt(x)) Pretty good so far. The only trouble is that the type of x is inconsistent. In f it is an integer, but in primeQ it is a floating point (because you are taking its square root). Getting past this just involves understanding Haskell's type system peculiarities. Change that last line to: where y = floor (sqrt (fromIntegral x)) And you should be fine. (Untested) In the future, post the error that you are getting addition to the code that is causing it. That helps us find it faster. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] FRP for game programming / artifical life simulation

On Wed, Apr 21, 2010 at 4:47 PM, Ben Christy ben.chri...@gmail.com wrote: I have an interest in both game programming and artificial life. I have recently stumbled on Haskell and would like to take a stab at programming a simple game using FRP such as YAMPA or Reactive but I am stuck. I am not certain which one I should choose. It seems that Reactive is more active but is it suitable for game programming. Also has anyone attempted to implement neural networks using FRP if so again which of these two approaches to FRP would you suggest? I am in the process of writing a game using FRP. I haven't followed reactive in a while, but last I checked it had some rather annoying issues, such as joinE (monad join on events) not working and an open space leak. So we are using a Yampa-like approach, but not specifically Yampa. However most of the game logic is *not* in AFRP (arrowized FRP) style, it is just there to give a nice foundation and top level game loop, playing much the same role as IO does in many Haskell programs (but it is implemented purely!). The workhorse of our game has so far been generalized differentials. While not entirely rigorous, they have provided a very nice framework in which to express our thoughts and designs, and are very good at highly dynamic situations which appear in games. For example, with arrows it is painful to maintain a list of moving actors such that can be added and removed. With differentials this is quite natural. I haven't published the differential library yet, I am waiting until we have used them enough to discover essential techniques and find a nice bases for primitives. But I will give a sketch here. Let the types be your guide, as I am implementing from memory without a compiler :-P import qualified Data.Accessor.Basic as Acc import Data.VectorSpace import Control.Comonad A differential is implemented as a function that takes a timestep and returns an update function. Don't expose the D constructor; step is okay to expose, it's kind of a generalized linear approximation. newtype D a = D { step :: Double - a - a } instance Monoid (D a) where mempty = D (const id) mappend da db = D (\dt - step da dt . step db dt) Given a differential for a component of a value, we can construct a differential for that value. accessor :: Acc.T s a - D a - D s accessor acc da = D (Acc.modify acc . step da) Given a differential for each component of a tuple, we can find the differential for the tuple. product :: D a - D b - D (a, b) product da db = D (\dt (x,y) - (step da dt x, step db dt y)) A differential can depend on the current value. dependent :: (a - D a) - D a dependent f = D (\dt x - step (f x) dt x) Vectors can be treated directly as differentials over themselves. vector :: (VectorSpace v, Scalar v ~ Double) = v - D v vector v = D (\dt x - x ^+^ dt *^ v) Impulses allow non-continuous burst changes, such as adding/removing an element from a list of actors. This is the only function that bugs me. Incorrectly using it you can determine the framerate, which is supposed be hidden. But if used correctly; i.e. only trigger them on passing conditions, they can be quite handy. But my eyes and ears are open for alternatives. impulse :: (a - a) - D a impulse f = D (const f) If we can can find the differential for an element of some comonad given its context, we can find the differential for the whole structure. (Our game world is a comonad, that's why this is in here) comonad :: (Comonad w) = (w a - D a) - D (w a) comonad f = D (\dt - let h w = step (f w) dt (extract w) in extend h) I add new primitives at the drop of a hat. I would like to find a nice combinator basis, but as yet, one hasn't jumped out at me. It might require some tweaking of the concept. The arrow we are using is implemented in terms of differentials: data Continuous a b = forall s. Continuous s (s - a - (b, D s)) instance Category Continuous where id = Continuous () (\() x - (x, mempty)) Continuous sg0 g . Continuous sf0 f = MkC (sg0,sf0) $ \(sg,sf) x - let !(y, df) = f sf x -- mind the strict patterns !(z, dg) = g sg y in (z, product dg df) Exercise: implement the Arrow and ArrowLoop instances. And here is where it comes together. Integration over generalized differentials is a continuous arrow: integral :: Continuous (D a) a integral a0 = Continuous a0 (,) So our game loop looks something like: dGameState :: Input - D GameState dGameState = ... -- built out of simpler Ds of its components mainGame = proc input - do gameState - integral initialGameState - dGameState input returnA - drawGameState gameState This is my first experience with functional game programming, and so far I love it! It makes so much more sense than the imperative alternative. But the techniques are quite new and different as well, and sometimes it takes a lot of thinking to figure out how to do something that

### Re: [Haskell-cafe] Re: instance Eq (a - b)

On Wed, Apr 14, 2010 at 4:41 AM, rocon...@theorem.ca wrote: As ski noted on #haskell we probably want to extend this to work on Compact types and not just Finite types instance (Compact a, Eq b) = Eq (a - b) where ... For example (Int - Bool) is a perfectly fine Compact set that isn't finite and (Int - Bool) - Int has a decidable equality in Haskell (which Oleg claims that everyone knows ;). I don't know off the top of my head what the class member for Compact should be. I'd guess it should have a member search :: (a - Bool) - a with the specificaiton that p (search p) = True iff p is True from some a. But I'm not sure if this is correct or not. Maybe someone know knows more than I do can claify what the member of the Compact class should be. http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ Here is a summary of my prelude for topology-extras, which never got cool enough to publish. -- The sierpinski space. Two values: T and _|_ (top and bottom); aka. halting and not-halting. -- With a reliable unamb we could implement this as data Sigma = Sigma. -- Note that negation is not a computable function, so we for example split up equality and -- inequality below. data Sigma (\/) :: Sigma - Sigma - Sigma -- unamb (/\) :: Sigma - Sigma - Sigma -- seq class Discrete a where -- equality is observable (===) :: a - a - Sigma class Hausdorff a where -- inequality is observable (=/=) :: a - a - Sigma class Compact a where -- universal quantifiers are computable forevery :: (a - Sigma) - Sigma class Overt a where -- existential quantifiers are computable forsome :: (a - Sigma) - Sigma instance (Compact a, Discrete b) = Discrete (a - b) where f === g = forevery $ \x - f x === g x instance (Overt a, Hausdorff b) = Hausdorff (a - b) where f =/= g = forsome $ \x - f x =/= g x By Tychonoff's theorem we should have: instance (Compact b) = Compact (a - b) where forevert p = ??? But I am not sure whether this is computable, whether (-) counts as a product topology, how it generalizes to ASD-land [1] (in which I am still a noob -- not that I am not a topology noob), etc. Luke [1] Abstract Stone Duality -- a formalization of computable topology. http://www.paultaylor.eu/ASD/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: instance Eq (a - b)

On Wed, Apr 14, 2010 at 5:13 AM, Luke Palmer lrpal...@gmail.com wrote: On Wed, Apr 14, 2010 at 4:41 AM, rocon...@theorem.ca wrote: As ski noted on #haskell we probably want to extend this to work on Compact types and not just Finite types instance (Compact a, Eq b) = Eq (a - b) where ... For example (Int - Bool) is a perfectly fine Compact set that isn't finite and (Int - Bool) - Int has a decidable equality in Haskell (which Oleg claims that everyone knows ;). I don't know off the top of my head what the class member for Compact should be. I'd guess it should have a member search :: (a - Bool) - a with the specificaiton that p (search p) = True iff p is True from some a. But I'm not sure if this is correct or not. Maybe someone know knows more than I do can claify what the member of the Compact class should be. http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ Here is a summary of my prelude for topology-extras, which never got cool enough to publish. -- The sierpinski space. Two values: T and _|_ (top and bottom); aka. halting and not-halting. -- With a reliable unamb we could implement this as data Sigma = Sigma. -- Note that negation is not a computable function, so we for example split up equality and -- inequality below. data Sigma (\/) :: Sigma - Sigma - Sigma -- unamb (/\) :: Sigma - Sigma - Sigma -- seq class Discrete a where -- equality is observable (===) :: a - a - Sigma class Hausdorff a where -- inequality is observable (=/=) :: a - a - Sigma class Compact a where -- universal quantifiers are computable forevery :: (a - Sigma) - Sigma class Overt a where -- existential quantifiers are computable forsome :: (a - Sigma) - Sigma instance (Compact a, Discrete b) = Discrete (a - b) where f === g = forevery $ \x - f x === g x instance (Overt a, Hausdorff b) = Hausdorff (a - b) where f =/= g = forsome $ \x - f x =/= g x Elaborating a little, for Eq we need Discrete and Hausdorff, together with some new primitive: -- Takes x and y such that x \/ y = T and x /\ y = _|_, and returns False if x = T and True if y = T. decide :: Sigma - Sigma - Bool Escardo's searchable monad[1][2] from an Abstract Stone Duality perspective actually encodes compact *and* overt. (a - Bool) - a seems a good basis, even though it has a weird spec (it gives you an a for which the predicate returns true, but it's allowed to lie if there is no such a). (a - Bool) - Maybe a seems more appropriate, but it does not compose well. I am not sure how I feel about adding an instance of Eq (a - b). All this topology stuff gets a lot more interesting and enlightening when you talk about Sigma instead of Bool, so I think any sort of Compact constraint on Eq would be a bit ad-hoc. The issues with bottom are subtle and wishywashy enough that, if I were writing the prelude, I would be wary of providing any general mechanism for comparing functions, leaving those decisions to be tailored to the specific problem at hand. On the other hand, with a good unamb (pleez?) and Sigma, I think all these definitions make perfect sense. I think the reason I feel that way is that in Sigma's very essence lies the concept of bottom, whereas with Bool sometimes we like to pretend there is no bottom and sometimes we don't. [1] On hackage: http://hackage.haskell.org/package/infinite-search [2] Article: http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/ By Tychonoff's theorem we should have: instance (Compact b) = Compact (a - b) where forevert p = ??? But I am not sure whether this is computable, whether (-) counts as a product topology, how it generalizes to ASD-land [1] (in which I am still a noob -- not that I am not a topology noob), etc. Luke [1] Abstract Stone Duality -- a formalization of computable topology. http://www.paultaylor.eu/ASD/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Announce: hothasktags

On Wed, Apr 7, 2010 at 1:23 AM, Evan Laforge qdun...@gmail.com wrote: On Thu, Apr 1, 2010 at 1:46 PM, Luke Palmer lrpal...@gmail.com wrote: Hi, I'd like to draw attention to a little script I wrote. I tend to use qualified imports and short names like new and filter. This makes hasktags pretty much useless, since it basically just guesses which one to go to. hothasktags is a reimplementation of hasktags that uses haskell-src-exts to analyze the import structure to generate (scoped) tags pointing to the right definition. I'm pretty addicted to it, since it provides the only functionality I miss from visual studio :-). VIm only for now, since I don't know if emacs tags format supports scoped tags. I am aware that it is not perfect -- patches and bug reports welcome. Hi, thanks for this, I've been wanting something like this for a long time! I have a suggestion and a question though: If you prepend the tags file with !_TAG_FILE_SORTED\t1\t ~\n then I think vim should be able to do a binary search on the file. Thanks! This program generates a tag for each reference to a symbol: Almost. It generates a tag for each file/symbol pair such that the symbol is accessible from the file. Derive.PitchDeriver Derive/Derive.hs 98; file:Cmd/Cmd.hs Derive.PitchDeriver Derive/Derive.hs 98; file:Cmd/Play.hs Derive.PitchDeriver Derive/Derive.hs 98; file:Cmd/ResponderSync.hs ... [ 20 more ] ... The vim tag documentation says these are static tags, and implies they are meant to apply to symbols only valid within the same file, but this is clearly not the case. Actually, the vim doc implies that only file: is defined, and doesn't talk about scoped tags so I'm not sure what is going on. Anyway, whenever I go to a tag I have to first step through a message that says 1 of 25 or so. There's one for each reference in the tags file, even though those are references in other files. Hmm odd, I don't get that behavior. Is that with the sorted annotation? What version of vim? What's going on? I even checked the current docs at vim.org and they don't mention a file:xyz form either. I think I saw it documented *somewhere*, but now that I look again I can't find it anywhere. Maybe it was in a dream. I hope a newer version of vim didn't remove the support or something... Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Hackage accounts and real names

On Mon, Apr 5, 2010 at 9:18 PM, Ertugrul Soeylemez e...@ertes.de wrote: David House dmho...@gmail.com wrote: * Reputation. Using a RealName is the most credible way to build a combined online and RealLife identity. (Some people don't want this, for whatever reasons.) I agree that the restriction should be lifted. A lot of very smart people do not want their real names connected to certain projects or be found on the internet at all. And I don't agree that why not? can be a valid argument, but even if it is, the above is a valid answer to it. So all in all there is no convincing argument for the restriction, but at least two convincing arguments against. When you say convincing, you are talking about yourself being convinced, right? So this paragraph means The arguments against my position haven't convinced me, but the arguments for my position have. Human identity is much more than just a file descriptor or a map key, and people from academia often don't get this, because they don't have to fear using their real names. Particularly in economically illiberal countries being known as the author of a certain Haskell package can get you into trouble either at work or even with the government. It can also prevent you from getting a job. Nobody should be forced to use their real name anywhere on the internet, because unlike a bulletin board in a university, lab or school, the internet can be searched by employers easily. Greets Ertugrul -- nightmare = unsafePerformIO (getWrongWife = sex) http://blog.ertes.de/ ___ 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] Announce: hothasktags

Hi, I'd like to draw attention to a little script I wrote. I tend to use qualified imports and short names like new and filter. This makes hasktags pretty much useless, since it basically just guesses which one to go to. hothasktags is a reimplementation of hasktags that uses haskell-src-exts to analyze the import structure to generate (scoped) tags pointing to the right definition. I'm pretty addicted to it, since it provides the only functionality I miss from visual studio :-). VIm only for now, since I don't know if emacs tags format supports scoped tags. I am aware that it is not perfect -- patches and bug reports welcome. http://hackage.haskell.org/package/hothasktags Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Re: Are there any female Haskellers?

2010/3/28 Pekka Enberg penb...@cs.helsinki.fi: 2010/3/28 Günther Schmidt gue.schm...@web.de: This is definately a point where we will continue to disagree. I found myself assuming that there are no female haskellers and wanted to verify it by asking for data. So what exactly is off-topic for this list? Is unsubscribing from the list the only option to get rid of this kind of utter nonsense posts that contain absolutely zero valuable discussion on _Haskell_? It sounds like you are complaining because people are not talking about what you want them to be talking about. This will happen in large groups. Use a decent mail reader so that such nonsense posts are only one keypress away from the garbage. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

### Re: [Haskell-cafe] Are there any female Haskellers?

On Sat, Mar 27, 2010 at 2:22 PM, Peter Verswyvelen bugf...@gmail.com wrote: So the first computer nerd was a women??!!! ;-) ;-) ;-) Yeah, and she was so attractive that the entire male gender spent the next 50 years trying to impress her. Luke On Sat, Mar 27, 2010 at 9:06 PM, John Van Enk vane...@gmail.com wrote: http://en.wikipedia.org/wiki/Grace_Hopper A heck of a lady. On Sat, Mar 27, 2010 at 12:51 PM, Andrew Coppin andrewcop...@btinternet.com wrote: Ozgur Akgun wrote: Nevertheless, I guess you're right. There are very few females in most of the CS topics, and haskell is no different. This is my experience too. Although note that apparently the world's very first computer programmer was apparently a woman... ___ 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 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] Parsec monad transformer with IO?

On Thu, Mar 18, 2010 at 10:37 AM, Stefan Klinger all-li...@stefan-klinger.de wrote: Hello! Nice, Parsec 3 comes with a monad transformer [1]. So I thought I could use IO as inner monad, and perform IO operations during parsing. But I failed. Monad transformers still bend my mind. My problem: I don't see a function to actually lift the IO operation into the ParsecT. It should be something like lift :: IO a - ParsecT s u IO a That operation, with that name, and (a generalization of) that type, is *the* method of the MonadTrans class. Essentially the presence of that operation is the definition of what it means to be a monad transformer. The following is a toy example, I just could not make something smaller: Let's parse command line arguments (tokens are Strings), and execute them while parsing. import Text.Parsec.Prim import Text.Parsec.Pos import Text.Parsec import System.Environment ( getArgs ) Command line interface parser (Clip) type: Inner monad IO, user state u, tokens are Strings, returns something typed a. type Clip u a = ParsecT [String] u IO a Source code position for command line arguments: The line is always 1, column n represents the n-th command line argument. nextPos p _ _ = incSourceColumn p 1 Two primitive parsers, one for flags (with a dash) and one for other arguments: clipFlag x accepts the command line flag -x, and returns x. clipFlag :: String - Clip u String clipFlag x = tokenPrim id nextPos (\y - if '-':x == y then Just x else Nothing) clipValue accepts any command line argument that does not tart with a dash '-'. clipValue :: Clip u String clipValue = tokenPrim id nextPos test where test ('-':_) = Nothing test other = Just other Now the test program: Load files given on the command line, and sum up their word count, until -p is given. -p prints the current word count and sets the counter to zero. Further files may be processed then. At the end, show the sum of all word counts. Example: foo has 12 words, bar has 34 words: main foo -p bar -p foo bar -p Counted 12 words, reset counter. Counted 34 words, reset counter. Counted 46 words, reset counter. Grand total: 92 type CurrentCount = Int -- the user state used with Clip/ParsecT. root implements the command line grammar (filename+ -p)* and returns the sum of all word counts. root :: Clip CurrentCount Int root = do ns - many (many1 loadFile printSize) eof return $ sum ns Interprets each non-flag on the command line as filename, loads it, counts its words, and adds the count to the state. loadFile :: Clip CurrentCount () loadFile = do -- expect a filename filename - clipValue -- load the file: IO content - lift $ readFile filename -- add wordcount to state modifyState ((+) (length $ words content)) If -p shows up on the command line, print accumulated count, reset counter to cero and return count for grand-total calculation. printSize :: Clip CurrentCount Int printSize = do -- expect flag -p clipFlag p -- print current word count: IO n - getState lift . putStrLn $ Counted ++show n++ words, reset counter. -- reset user state to zero, return word count for grand total putState 0 return n main just runs the root parser on the command line arguments and checks the result. main = do result - getArgs = runParserT root 0 command line case result of Left err - error $ show err Right n - putStrLn $ Grand total: ++show n So where is the lift function? Does it exist? Here, I need your help. lift :: IO a - ParsecT s u IO a lift = undefined Any comments are appreciated. Thank you! Stefan [1] http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Parsec-Prim.html#t:ParsecT -- Stefan Klinger o/klettern /\/ bis zum send plaintext only - max size 32kB - no spam \ Abfallen http://stefan-klinger.de ___ 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] Abstraction in data types

On Thu, Mar 18, 2010 at 12:17 PM, John Meacham j...@repetae.net wrote: On Wed, Mar 17, 2010 at 09:20:49PM -0700, Darrin Chandler wrote: data Point = Cartesian (Cartesian_coord, Cartesian_coord) | Spherical (Latitude, Longitude) Just a quick unrelated note, though you are probably aware of this, doing data Foo = Foo (X,Y) means something subtly different than data Foo = Foo X Y and can be less efficient. On the other hand, the latter is equivalent to: newtype Foo = Foo (X,Y) A quick way to see they are different is to count the bottoms, in the first case (where _ is bottom and X is some value) you have the cases Foo _ Foo (_,_) Foo (X,_) Foo (_,X) Foo (X,X) and in the other case you have Foo _ _ Foo X _ Foo _ X Foo X X so one has 5 distinct values, and the other has 4, hence they are not isomorphic. All things being equal, this means the second case will be more efficient as there is one less case it needs to distinguish (every potential bottom implys an 'eval' somewhere). Depending on your code, all things may not be equal and there are rare times when the tupled version is more efficient however. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ 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