- Haskell-Cafe - Haskell.org

Regular Expression Parsing via derivatives
by Alex Clemmer 02 Sep '11

02 Sep '11

Hi Haskell people, I've been snooping through various mailing lists and the current Haskell implementation of regular expressions and I was wondering if there has been a discussion about implementing regex parsing with derivatives. If so, I haven't seen it. If not, I'd like to have a discussion about it -- if for no other reason than to decide whether I should implement it as a library, or (to attempt to implement it) as a core feature. For those of you who don't know, recent work by Might and Darais<http://arxiv.org/abs/1010.5023>indicates that parsing CFGs can be done better ( *i.e.*, significantly faster) than more "traditional" approaches<http://swtch.com/%7Ersc/regexp/regexp1.html>. Might's presenting at ICFP later in September about it. I guess the first thing I should ask is, which mailing list is actually the right place to field this inquiry. I considered dropping it in the main haskell list, but wasn't sure how people would respond. -- Alex

5 5

Finger Tree without using Monoid
by Xinyu LIU 02 Sep '11

02 Sep '11

Hi, I was trying to implement MTF (move-to-front) algorithm, However, neither Array nor List satisfied all aspects. Array: Although the random access is O(1), However, move an element to front takes O(N) in average; List: Although move to front is O(1), However, random access takes O(N) in average; I dig out the paper [1] and find the Finger Tree solution. There is already good Finger Tree implementation in Haskell as Data.Sequence [2] based on [3]. I wrote a simple version based on the original paper, but avoid using Monoid when augment (or cache) the size of the tree. The idea is to wrap every element as a leaf of node. This idea is similar to the Chris Okasaki's binary random access list [4]. As one test case, I tested move to front with Finger Tree. Here is the code (sorry for a bit long): >>> module FingerTree where import Test.QuickCheck data Node a = Br Int [a] deriving (Show) -- size, branches data Tree a = Empty | Lf a | Tr Int [a] (Tree (Node a)) [a] -- size, front, middle, rear deriving (Show) type FList a = Tree (Node a) -- Auxiliary functions for calculate size of node and tree size :: Node a -> Int size (Br s _) = s sizeL :: [Node a] -> Int sizeL = sum .(map size) sizeT :: FList a -> Int sizeT Empty = 0 sizeT (Lf a) = size a sizeT (Tr s _ _ _) = s -- Auxiliary functions for building and unboxing node(s) wrap :: a -> Node a wrap x = Br 1 [x] unwrap :: Node a -> a unwrap (Br 1 [x]) = x wraps :: [Node a] -> Node (Node a) wraps xs = Br (sizeL xs) xs unwraps :: Node a -> [a] unwraps (Br _ xs) = xs -- Helper function for building tree tree :: [Node a] -> FList (Node a) -> [Node a] -> FList a tree f Empty [] = foldr cons' Empty f tree [] Empty r = foldr cons' Empty r tree [] m r = let (f, m') = uncons' m in tree (unwraps f) m' r tree f m [] = let (m', r) = unsnoc' m in tree f m' (unwraps r) tree f m r = Tr (sizeL f + sizeT m + sizeL r) f m r -- Operations at the front of the sequence cons :: a -> FList a -> FList a cons a t = cons' (wrap a) t cons' :: (Node a) -> FList a -> FList a cons' a Empty = Lf a cons' a (Lf b) = tree [a] Empty [b] cons' a (Tr _ [b, c, d, e] m r) = tree [a, b] (cons' (wraps [c, d, e]) m) r cons' a (Tr _ f m r) = tree (a:f) m r uncons :: FList a -> (a, FList a) uncons ts = let (t, ts') = uncons' ts in (unwrap t, ts') uncons' :: FList a -> ((Node a), FList a) uncons' (Lf a) = (a, Empty) uncons' (Tr _ [a] Empty [b]) = (a, Lf b) uncons' (Tr _ [a] Empty (r:rs)) = (a, tree [r] Empty rs) uncons' (Tr _ [a] m r) = (a, tree (unwraps f) m' r) where (f, m') = uncons' m uncons' (Tr _ (a:f) m r) = (a, tree f m r) head' :: FList a -> a head' = fst . uncons tail' :: FList a -> FList a tail' = snd . uncons -- Operations at the rear of the sequence snoc :: FList a -> a -> FList a snoc t a = snoc' t (wrap a) snoc' :: FList a -> Node a -> FList a snoc' Empty a = Lf a snoc' (Lf a) b = tree [a] Empty [b] snoc' (Tr _ f m [a, b, c, d]) e = tree f (snoc' m (wraps [a, b, c])) [d, e] snoc' (Tr _ f m r) a = tree f m (r++[a]) unsnoc :: FList a -> (FList a, a) unsnoc ts = let (ts', t) = unsnoc' ts in (ts', unwrap t) unsnoc' :: FList a -> (FList a, (Node a)) unsnoc' (Lf a) = (Empty, a) unsnoc' (Tr _ [a] Empty [b]) = (Lf a, b) unsnoc' (Tr _ f@(_:_) Empty [a]) = (tree (init f) Empty [last f], a) unsnoc' (Tr _ f m [a]) = (tree f m' (unwraps r), a) where (m', r) = unsnoc' m unsnoc' (Tr _ f m r) = (tree f m (init r), (last r)) last' :: FList a -> a last' = snd . unsnoc init' :: FList a -> FList a init' = fst . unsnoc -- Concatenation concat' :: FList a -> FList a -> FList a concat' t1 t2 = merge t1 [] t2 merge :: FList a -> [Node a] -> FList a -> FList a merge Empty ts t2 = foldr cons' t2 ts merge t1 ts Empty = foldl snoc' t1 ts merge (Lf a) ts t2 = merge Empty (a:ts) t2 merge t1 ts (Lf a) = merge t1 (ts++[a]) Empty merge (Tr s1 f1 m1 r1) ts (Tr s2 f2 m2 r2) = Tr (s1 + s2 + (sizeL ts)) f1 (merge m1 (nodes (r1 ++ ts ++ f2)) m2) r2 nodes :: [Node a] -> [Node (Node a)] nodes [a, b] = [wraps [a, b]] nodes [a, b, c] = [wraps [a, b, c]] nodes [a, b, c, d] = [wraps [a, b], wraps [c, d]] nodes (a:b:c:xs) = (wraps [a, b, c]):nodes xs -- Splitting splitAt' :: Int -> FList a -> (FList a, Node a, FList a) splitAt' _ (Lf x) = (Empty, x, Empty) splitAt' i (Tr _ f m r) | i < szf = let (xs, y, ys) = splitNodesAt i f in ((foldr cons' Empty xs), y, tree ys m r) | i < szf + szm = let (m1, t, m2) = splitAt' (i-szf) m (xs, y, ys) = splitNodesAt (i-szf - sizeT m1) (unwraps t) in (tree f m1 xs, y, tree ys m2 r) | otherwise = let (xs, y, ys) = splitNodesAt (i-szf -szm) r in (tree f m xs, y, foldr cons' Empty ys) where szf = sizeL f szm = sizeT m splitNodesAt :: Int -> [Node a] -> ([Node a], Node a, [Node a]) splitNodesAt 0 [x] = ([], x, []) splitNodesAt i (x:xs) | i < size x = ([], x, xs) | otherwise = let (xs', y, ys) = splitNodesAt (i-size x) xs in (x:xs', y, ys) -- Random access operations getAt :: FList a -> Int -> a getAt t i = unwrap x where (_, x, _) = splitAt' i t extractAt :: FList a -> Int -> (a, FList a) extractAt t i = let (l, x, r) = splitAt' i t in (unwrap x, concat' l r) setAt :: FList a -> Int -> a -> FList a setAt t i x = let (l, _, r) = splitAt' i t in concat' l (cons x r) -- move the i-th element to front moveToFront :: FList a -> Int -> FList a moveToFront t i = let (a, t') = extractAt t i in cons a t' -- auxiliary functions fromList :: [a] -> FList a fromList = foldr cons Empty toList :: FList a -> [a] toList Empty = [] toList t = (head' t):(toList $ tail' t) -- testing prop_cons :: [Int] -> Bool prop_cons xs = xs == (toList $ fromList xs) prop_snoc :: [Int] -> Bool prop_snoc xs = xs == (toList' $ foldl snoc Empty xs) where toList' Empty = [] toList' t = (toList' $ init' t)++[last' t] prop_concat :: [Int]->[Int]->Bool prop_concat xs ys = (xs ++ ys) == (toList $ concat' (fromList xs) (fromList ys)) prop_lookup :: [Int] -> Int -> Property prop_lookup xs i = (0 <=i && i < length xs) ==> (getAt (fromList xs) i) == (xs !! i) prop_update :: [Int] -> Int -> Int -> Property prop_update xs i y = (0 <=i && i < length xs) ==> toList (setAt (fromList xs) i y) == xs' where xs' = as ++ [y] ++ bs (as, (_:bs)) = splitAt i xs prop_mtf :: [Int] -> Int -> Property prop_mtf xs i = (0 <=i && i < length xs) ==> (toList $ moveToFront (fromList xs) i) == mtf where mtf = b : as ++ bs (as, (b:bs)) = splitAt i xs <<< It can be found at: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/elementary/arra… [Reference] [1]. Jon Bentley, Daniel Sleator, Robert Tarjan, Victor Wei. "A locally adaptive data compression scheme." Communication of the ACM.1986. [2]. http://hackage.haskell.org/packages/archive/fingertree/0.0/doc/html/Data-Fi… [3]. Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", *Journal of Functional Programming* 16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html [4]. Purely Functional Random-Access Lists by Chris Okasaki. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95. -- Larry, LIU Xinyu https://sites.google.com/site/algoxy/ https://github.com/liuxinyu95/AlgoXY

4 3

Is it a bug in haskell-src-meta package?
by bob zhang 01 Sep '11

01 Sep '11

Hi, all parseExp "(,) 3 4 " => Right (AppE (AppE (ConE GHC.Unit.(,)) (LitE (IntegerL 3))) (LitE (IntegerL 4))) where's GHC.Unit.(,) ? Many thanks best, bob

3 6

Pointed, but not Applicative
by Sönke Hahn 01 Sep '11

01 Sep '11

Hi! I was reading through the Typeclassopedia ([1]) and I was wondering which type could be an instance of Pointed, but not of Applicative. But I can't think of one. Any ideas? Sönke [1] http://www.haskell.org/haskellwiki/Typeclassopedia

8 16

Data structure
by yrazes 01 Sep '11

01 Sep '11

Hi guys, I want to compare data structure between Haskell, Java, Lisp and C. I am wondering if I could compare list comprehention in haskell with the vector class in Java, macros in common lisp and dynamic arrays in C. Thanks, Julita

2 2

Haskell Weekly News: Issue 197
by Daniel Santa Cruz 31 Aug '11

31 Aug '11

Welcome to issue 197 the HWN, a newsletter covering developments in the Haskell community. This release covers the week of August 21 to 27, 2011. [1] http://goo.gl/8hDku Announcements Liyang HU announced HakkaTaikai, a Haskell hackathon in Tokyo, on Sunday September 25th, 2011. [2] http://goo.gl/tJ4F4 Qiuchi Jian wondered if anyone would be interested in joining him in translating the 2010 Haskell Report into Chinese. [3] http://goo.gl/QDdeF Johan Tibell announced the results of this year's "State of Haskell" survey. [4] http://goo.gl/26Evg New and Updated Projects * network-address (New - Sebastian Nowicki) Provides data structures for IP addresses as well as subnetworks. [5] http://goo.gl/LTuUK * shelltestrunner (Update - Simon Michael) Tests command-line programs or arbitrary shell commands. [6] http://goo.gl/uKHMo * netwire (Update - Ertugrul Soeylemez) An arrowized functional reactive programming library written with networking applications in mind. [7] http://goo.gl/yM0hy * instinct (New - Ertugrul Soeylemez) Library for neural networks. [8] http://goo.gl/yM0hy Quotes of the Week * elliott: i'm here to prove theorems and compile code and I'm all out of code * shachaf: To deepSeq is a fundamental right * djahandarie: I wonder if De Bruijn was any good at remembering names. * JaffaCake: In the beginning there were 8 registers, and That Was Enough For Everyone. * frezik: "The compiler accepted it, why can't you?" * Cale: the units of the monoids in the algebras for the monoid monad * _Ray_: fucking hell, math and cs need to stop having awesome interesting things. it's ruining my life. * accel: next time I'll read a few research papers before I start trolling hakell * ddarius: isJust :: Maybe a -> Bool; isJust = unsafeCoerce Top Reddit Stories * Interested in a 2nd edition of "Real World Haskell"? Domain: self.haskell, Score: 130, Comments: 33 On Reddit: [9] http://goo.gl/fNS6P Original: [10] http://goo.gl/fNS6P * GHC on ARM: Merged into GHC HEAD Domain: ghcarm.wordpress.com, Score: 78, Comments: 7 On Reddit: [11] http://goo.gl/BvFvX Original: [12] http://goo.gl/ZKDYx * Why Haskell is Kinda Cool Domain: amtal.github.com, Score: 56, Comments: 27 On Reddit: [13] http://goo.gl/9ealD Original: [14] http://goo.gl/0AJIn * Haskell for Kids: Week 2! Domain: cdsmith.wordpress.com, Score: 55, Comments: 20 On Reddit: [15] http://goo.gl/0Qm5z Original: [16] http://goo.gl/DzdUy * Results from the State of Haskell, 2011 Survey Domain: blog.johantibell.com, Score: 54, Comments: 18 On Reddit: [17] http://goo.gl/BAQye Original: [18] http://goo.gl/l6sc1 * PyPy: We need Software Transactional Memory Domain: morepypy.blogspot.com, Score: 49, Comments: 2 On Reddit: [19] http://goo.gl/6dPjT Original: [20] http://goo.gl/kNCma * mmmodularity! - A modular package language for Haskell Domain: skilpat.tumblr.com, Score: 48, Comments: 8 On Reddit: [21] http://goo.gl/6dfSf Original: [22] http://goo.gl/os9IJ * A Tutorial Introduction to the Lambda Calculus Domain: utdallas.edu, Score: 34, Comments: 9 On Reddit: [23] http://goo.gl/OtPrs Original: [24] http://goo.gl/zTIx4 * Functional representation of Rubik's cube Domain: pnyf.inf.elte.hu, Score: 30, Comments: 3 On Reddit: [25] http://goo.gl/TMOnc Original: [26] http://goo.gl/EoYbu * monad-control, for more flexible transformers Domain: yesodweb.com, Score: 27, Comments: 14 On Reddit: [27] http://goo.gl/XF6GZ Original: [28] http://goo.gl/ijd6V * A different haskell emacs mode (work in progress) Domain: chrisdone.com, Score: 26, Comments: 5 On Reddit: [29] http://goo.gl/lfmxF Original: [30] http://goo.gl/7qvho Top StackOverflow Questions * Haskell: How does non-strict and lazy differ? votes: 25, answers: 5 Read on SO: [31] http://goo.gl/2KJVY * forall in Scala votes: 18, answers: 5 Read on SO: [32] http://goo.gl/ejOwF * What is the name of this monad-like functional programming pattern? votes: 16, answers: 1 Read on SO: [33] http://goo.gl/Rv1BC * Is (reverse . f . reverse) efficient? votes: 11, answers: 4 Read on SO: [34] http://goo.gl/U7qLu * Haskell Space Overflow votes: 8, answers: 4 Read on SO: [35] http://goo.gl/5uBY2 * How to write recursive lambda expression in Haskell? votes: 8, answers: 2 Read on SO: [36] http://goo.gl/TokK2 * Is the random number generator in Haskell thread-safe? votes: 8, answers: 4 Read on SO: [37] http://goo.gl/ERVpl * How can I create a tuple where each of the members are compared by an expression? votes: 7, answers: 5 Read on SO: [38] http://goo.gl/BiUpC * Haskell cartesian product of infinite lists votes: 7, answers: 4 Read on SO: [39] http://goo.gl/DC9M5 * How to implement a generic hierarchy of structures with injected functionality votes: 7, answers: 6 Read on SO: [40] http://goo.gl/IoMT6 About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18899 3. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/91853 4. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18894 5. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18893 6. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18900 7. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/91845 8. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/91845 9. http://www.reddit.com/r/haskell/comments/jtdrz/interested_in_a_2nd_edition_… 10. http://www.reddit.com/r/haskell/comments/jtdrz/interested_in_a_2nd_edition_… 11. http://ghcarm.wordpress.com/2011/08/27/current-status-merged-into-ghc-head/ 12. http://www.reddit.com/r/haskell/comments/jwgxj/ghc_on_arm_merged_into_ghc_h… 13. http://amtal.github.com/2011/08/25/why-haskell-is-kinda-cool.html 14. http://www.reddit.com/r/haskell/comments/juemg/why_haskell_is_kinda_cool/ 15. http://cdsmith.wordpress.com/2011/08/23/haskell-for-kids-week-2/ 16. http://www.reddit.com/r/haskell/comments/js4kd/haskell_for_kids_week_2/ 17. http://blog.johantibell.com/2011/08/results-from-state-of-haskell-2011.html 18. http://www.reddit.com/r/haskell/comments/jqfey/results_from_the_state_of_ha… 19. http://morepypy.blogspot.com/2011/08/we-need-software-transactional-memory.… 20. http://www.reddit.com/r/haskell/comments/jrprb/pypy_we_need_software_transa… 21. http://skilpat.tumblr.com/post/9411500320/a-modular-package-language-for-ha… 22. http://www.reddit.com/r/haskell/comments/jvlrw/mmmodularity_a_modular_packa… 23. http://www.utdallas.edu/~gupta/courses/apl/lambda.pdf 24. http://www.reddit.com/r/haskell/comments/jt0m1/a_tutorial_introduction_to_t… 25. http://pnyf.inf.elte.hu:8000/Rubik_en.xml 26. http://www.reddit.com/r/haskell/comments/jwfz2/functional_representation_of… 27. http://www.yesodweb.com/blog/2011/08/monad-control 28. http://www.reddit.com/r/haskell/comments/jtuk9/monadcontrol_for_more_flexib… 29. http://chrisdone.com/posts/2011-08-21-haskell-emacs.html 30. http://www.reddit.com/r/haskell/comments/js3sm/a_different_haskell_emacs_mo… 31. http://stackoverflow.com/questions/7140978/haskell-how-does-non-strict-and-… 32. http://stackoverflow.com/questions/7213676/forall-in-scala 33. http://stackoverflow.com/questions/7135540/what-is-the-name-of-this-monad-l… 34. http://stackoverflow.com/questions/7152183/is-reverse-f-reverse-efficient 35. http://stackoverflow.com/questions/7140732/haskell-space-overflow 36. http://stackoverflow.com/questions/7141229/how-to-write-recursive-lambda-ex… 37. http://stackoverflow.com/questions/7153255/is-the-random-number-generator-i… 38. http://stackoverflow.com/questions/7136921/how-can-i-create-a-tuple-where-e… 39. http://stackoverflow.com/questions/7141287/haskell-cartesian-product-of-inf… 40. http://stackoverflow.com/questions/7157841/how-to-implement-a-generic-hiera…

1 0

Re: [Haskell-cafe] Project Euler: request for comments
by KC 31 Aug '11

31 Aug '11

You also don't need mutual recursion for this explicit recursion since I imagine it would use up more stack space. -- Doing the one dimensional case. f011 :: [Int] -> Int f011 (t:u:v:xs) = f011helper t u v xs f011helper :: Int -> Int -> Int -> [Int] -> Int f011helper t u v (w:ws) | ws == [] = t*u*v*w | otherwise = max (t*u*v*w) (f011helper u v w ws) -- Note: f011helper does not call f011. On Mon, Aug 29, 2011 at 9:40 AM, Oscar Picasso <oscarpicasso(a)gmail.com> wrote: > Got it. > > f :: [Int] -> Int > f (t:u:v:xs) = helper t u v xs > > helper :: Int -> Int -> Int -> [Int] -> Int > helper t u v (w:ws) > | ws == [] = t*u*v*w > | otherwise = max (t*u*v*w) (f (u:v:w:ws)) > > I tend to overlook mutual recursion in my toolbox. Good going! :) > > Thanks for the enlightenment. > > On Sun, Aug 28, 2011 at 4:54 PM, KC <kc1956(a)gmail.com> wrote: >> Try something like the following: >> >> -- Project Euler 11 >> >> -- In the 20×20 grid below, four numbers along a diagonal line have >> been marked in red. >> >> -- <snip> >> >> -- The product of these numbers is 26 × 63 × 78 × 14 = 1788696. >> >> -- What is the greatest product of four adjacent numbers in any >> direction (up, down, left, right, or diagonally) in the 20×20 grid? >> >> >> import Data.List >> >> -- Doing the one dimensional case. >> f011 :: [Int] -> Int >> f011 (t:u:v:xs) = f011helper t u v xs >> >> f011helper :: Int -> Int -> Int -> [Int] -> Int >> f011helper t u v (w:ws) >> | ws == [] = t*u*v*w >> | otherwise = yada nada mada >> >> -- What are yada nada mada? >> >> -- The 20x20 grid case will become: >> f0112D :: [[Int]] -> Int >> -- where [[Int]] is a list of lists of rows, columns, major diagonals, >> & minor diagonals. >> -- -- Regards, KC

2 1

Re: [Haskell-cafe] Project Euler: request for comments
by KC 31 Aug '11

31 Aug '11

You might like this zipping & folding version. Explicit recursion has the disadvantage that one has to read the entire function in order to figure out what's going on; whereas using the higher order functions makes things much easier to grasp. listof4tuples xs = (zip4 xs (tail xs) (tail (tail xs)) (tail (tail (tail xs)))) prods xs = map prods4 (listof4tuples xs) prods4 (t,u,v,w) = t*u*v*w maxprods4 xs = maximum $ prods xs On Mon, Aug 29, 2011 at 9:40 AM, Oscar Picasso <oscarpicasso(a)gmail.com> wrote: > Got it. > > f :: [Int] -> Int > f (t:u:v:xs) = helper t u v xs > > helper :: Int -> Int -> Int -> [Int] -> Int > helper t u v (w:ws) > | ws == [] = t*u*v*w > | otherwise = max (t*u*v*w) (f (u:v:w:ws)) > > I tend to overlook mutual recursion in my toolbox. > > Thanks for the nnlightenment. > > On Sun, Aug 28, 2011 at 4:54 PM, KC <kc1956(a)gmail.com> wrote: >> Try something like the following: >> >> -- Project Euler 11 >> >> -- In the 20×20 grid below, four numbers along a diagonal line have >> been marked in red. >> >> -- <snip> >> >> -- The product of these numbers is 26 × 63 × 78 × 14 = 1788696. >> >> -- What is the greatest product of four adjacent numbers in any >> direction (up, down, left, right, or diagonally) in the 20×20 grid? >> >> >> import Data.List >> >> -- Doing the one dimensional case. >> f011 :: [Int] -> Int >> f011 (t:u:v:xs) = f011helper t u v xs >> >> f011helper :: Int -> Int -> Int -> [Int] -> Int >> f011helper t u v (w:ws) >> | ws == [] = t*u*v*w >> | otherwise = yada nada mada >> >> -- What are yada nada mada? >> >> -- The 20x20 grid case will become: >> f0112D :: [[Int]] -> Int >> -- where [[Int]] is a list of lists of rows, columns, major diagonals, >> & minor diagonals. >> >> >> >> >> On Sun, Aug 28, 2011 at 5:10 AM, Oscar Picasso <oscarpicasso(a)gmail.com> wrote: >>> No. The answer I posted is not good. >>> It worked, by chance, on a couple of small examples I tried but it >>> could end up comparing sequence of 4 numbers that where not initially >>> adjacent. >>> >>> On Sun, Aug 28, 2011 at 12:32 AM, Oscar Picasso <oscarpicasso(a)gmail.com> wrote: >>>> Maybe this? >>>> >>>> f x@(a:b:c:d:[]) = x >>>> f (a:b:c:d:e:ys) = if e >= a >>>> then f (b:c:d:e:ys) >>>> else f (a:b:c:d:ys) >>>> >>>> On Sat, Aug 27, 2011 at 8:26 PM, KC <kc1956(a)gmail.com> wrote: >>>>> Think of the simplest version of the problem that isn't totally trivial. >>>>> >>>>> e.g. A one dimensional list of numbers. >>>>> >>>>> What would you do? >>>>> >>>>> Note: you only want to touch each element once. >>>>> >>>>> The 2 dimensional case could be handled by putting into lists: rows, >>>>> columns, major diagonals, and minor diagonals. >>>>> >>>>> This isn't the fastest way of doing the problem but it has the >>>>> advantage of avoiding "indexitis". >>>>> >>>>> >>>>> On Fri, Aug 26, 2011 at 6:15 PM, Oscar Picasso <oscarpicasso(a)gmail.com> wrote: >>>>>> Like: >>>>>> 20*19*21*18 >>>>>> is bigger than >>>>>> 100*100*3*2 >>>>>> ? >>>>>> >>>>>> If so I need to think about how to formalize it. >>>>>> >>>>>> Thanks for the hint. >>>>>> >>>>>> On Fri, Aug 26, 2011 at 8:55 PM, KC <kc1956(a)gmail.com> wrote: >>>>>>> Is Problem 11 the 4 consecutive #'s problem? >>>>>>> >>>>>>> If so what must be true for 4 #'s to have a large product? >>>>>>> >>>>>>> Hint: x * y * z * 2 is that going to be larger? >>>>>>> >>>>>>> -- >>>>>>> -- >>>>>>> Regards, >>>>>>> KC >>>>>>> >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> -- >>>>> Regards, >>>>> KC >>>>> >>>> >>> >> >> >> >> -- >> -- >> Regards, >> KC >> > -- -- Regards, KC

2 1

Deriving laws by systematic transformations
by Armando Blancas 31 Aug '11

31 Aug '11

Studying Wadler's "Comprehending Monads" and "Theorems for free!", I've been unable to derive law (iv) and I'm not sure about (iii). Will appreciate a pointer to similar examples or a massive hint. Here's my attempt at (iii): map f . unit x = map f [x] = [f x] = unit (f x) = (unit . f) x map f . unit = unit .f >From the Monads article: unit :: x -> M x join :: M (M x) -> M x For example, unit 3 = [3] and join [[1,2], [3]] = [1,2,3] (iii) map f . unit = unit . f (iv) map f . join = join . map (map f) Laws (iii) and (iv) may be derived by systematic transformations of the polymorphic types of unit and join.

1 0

Off-topic: Mathematics
by Andrew Coppin 31 Aug '11

31 Aug '11

This is fairly wildly off-topic but... does anybody know of a good forum where I can ask questions about mathematics and get authoritative answers? (Apart from "go visit the nearest university", that is.)

11 22