Re: [Haskell-cafe] Programming Chalenges: The 3n+1 problem
Hi Dmitri, *** 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. Yet another option for memoization implementation: to use monad-memo package [1] which provides memoization for monadic function (using Data.Map by default). To use it we need to define our recursive function in monadic form and add `memo` in place of its recursive call: import Control.Applicative import Control.Monad.Memo -- calculates the length of sequence (with memoization) calcM 1 = return 1 calcM n = succ $ memo calcM (if even n then n `div` 2 else n*3 + 1) Here is a helper-function to run this calculation (we don't really need it here since `calcM` is going to be called from other monadic function directly): runCalc :: Integer - Integer runCalc = startEvalMemo . calcM NB: the inferred type for `calcM` might look a little bit.. verbose, but we don't really need to specify it or expose `calcM` from our module: calcM :: (MonadMemo a1 a m, Num a, Functor m, Integral a1, Enum a) = a1 - m a The implementation of the function to calculate the maximum length of the sequence for all numbers in a range is straightforward (and also monadic): -- NB: memoization cache is shared among all 'calcM' calls (very efficient) calcRangeM f t = maximum $ forM [f..t] calcM and a similar helper run-function (is not needed for the task either): runCalcRange :: Integer - Integer - Integer runCalcRange f t = startEvalMemo $ calcRangeM f t To run `calcRangeM` for the input list of values (map the function over it) we can define yet another simple monadic function which calls `calcRangeM` directly (thus reusing/building the same memoization cache): solM = mapM (uncurry calcRangeM) and a helper run-function: runSol :: [(Integer, Integer)] - [Integer] runSol = startEvalMemo . solM Composing all these together results in the following test code (I hard-coded the input for the sake of simplicity): import Control.Applicative import Control.Monad.Memo calcM 1 = return 1 calcM n = succ $ memo calcM (if even n then n `div` 2 else n*3 + 1) calcRangeM f t = maximum $ forM [f..t] calcM solM = mapM (uncurry calcRangeM) runSol = startEvalMemo . solM main = print $ runSol [ (1, 10), (100, 200), (201, 210), (900, 1000) ] As for the performance, `main = print $ runSol [(1, 100)]` takes ~40 seconds with -O2 on my laptop. [1] http://hackage.haskell.org/package/monad-memo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] checking types with type families
Simon Peyton-Jones wrote: I'm interested in situations where you think fundeps work and type families don't. Reason: no one knows how to make fundeps work cleanly with local type constraints (such as GADTs). If you think you have such as case, do send me a test case. As an example, is it possible to implement something like: http://okmij.org/ftp/Haskell/deepest-functor.lhs with TF only? I believe the following wiki-page http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap also points out that However, there's a problem: overlap is not allowed at all for type families!! (c) or is it just a question of implementing closed type families? -- View this message in context: http://old.nabble.com/checking-types-with-type-families-tp28967503p29049813.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
Re: [Haskell-cafe] type class constraints headache
Related question probably: why ghc compiles this:
{-# LANGUAGE RankNTypes, ImpredicativeTypes #-}
methods :: [(String, forall b. Eq b = b)]
methods =
[ (method1, undefined )
, (method2, undefined) ]
test:: [String]
test= pmap methods
where pmap = map fst
But when I change 'test' to:
test:: [String]
test= map fst methods
I get:
Cannot match a monotype with `forall b. (Eq b) = b'
Expected type: [(String, b)]
Inferred type: [(String, forall b1. (Eq b1) = b1)]
In the second argument of `map', namely `methods'
In the expression: map fst methods
Failed, modules loaded: none.
--
View this message in context:
http://old.nabble.com/type-class-constraints-headache-tp27752745p27779518.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
Re: [Haskell-cafe] Spelling checker exercise
Matthew Phillips-5 wrote: I also found it to to be very slow. My variant: http://a-ejeli-tak.livejournal.com/1326.html Spellchecker in Haskell String version runs in 2.5 sec, ByteString in 1.2 sec (just for one word e.g. just to build the tree). 8 sec to check input of 400 words (copied from Norvig's example). I think laziness helps here to avoid unnecessary checks (once the first match is found). Haven't tried it on a larger data sets neither tried to optimize it. Cheated on dictionary parsing though... -- View this message in context: http://old.nabble.com/Spelling-checker-exercise-tp27269320p27322382.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
Re: [Haskell-cafe] foldl in terms of foldr
Xingzhi Pan wrote: The first argument to foldr is of type (a - b - a), which takes 2 arguments. But 'step' here is defined as a function taking 3 arguments. What am I missing here? You can think of step as a function of two arguments which returns a function with one argument (although in reality, as any curried function, 'step' is _one_ argument function anyway): step :: b - (a - c) - (b - c) e.g. 'step' could have been defined as such: step x g = \a - g (f a x) to save on lambda 'a' was moved to argument list. -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27324376.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
Re: [Haskell-cafe] Spelling checker exercise
Daniel Fischer-4 wrote: But that's the point, these checks aren't unnecessary (unless the word under inspection is known). You want to propose the most likely correct word. I just wanted to rewrite original Nornig's Python code in Haskell :) (maybe I misunderstood the algorithm?). Of course it is far from being able to produce 'most likely correct' result. Btw, where can I find the source for this super-fast 'nLDBSWSpelling' variant? -- View this message in context: http://old.nabble.com/Spelling-checker-exercise-tp27269320p27324740.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
Re: [Haskell-cafe] foldl in terms of foldr
Neil Brown-7 wrote: step is of type b - (a - a) - (a - a), which does agree with (a - b - b) Not quite right.. Let's rewite the function: myFoldl f z xs = foldr (step f) id xs z step f x g = \a - g (f a x) now (from ghci): step (+) :: (Num t1) = t1 - (t1 - t3) - t1 - t3 or even: step (flip (:)) :: t - ([t] - t3) - [t] - t3 But yes, the type from my first post was wrong -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27325072.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
Re: [Haskell-cafe] foldl in terms of foldr
Xingzhi Pan wrote: More over, does foldr step f id xs z equal to foldr (step f) id xs z?? No, it does not. The former passes three-argument function 'step' to foldr and the later passes two-argument function which is the result of the partial application (step f). -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27325448.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
Re: [Haskell-cafe] foldl in terms of foldr
Eduard Sergeev wrote: The former passes three-argument function 'step' to foldr and the later passes two-argument function which is the result of the partial application (step f). Correction :) 4-arg and 3-arg respectively. -- View this message in context: http://old.nabble.com/foldl-in-terms-of-foldr-tp27322307p27325593.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
Re: [Haskell-cafe] Language simplicity
Andrew Coppin wrote: OK people, it's random statistics time! OK, my version of meaningless statistics: C++ (ISO/IEC 14882:1998(E)): 325 pages (712 including standard libraries) C# (ECMA-334): 505 pages (language only) Java: 450 pages (language only?) Scala (2.7): 125 pages (157 including standard library) Eiffel (ECMA-367): 160 pages (language only) ANSI SQL-92: 685 pages (language only) Haskell-98: 77 pages (247 including Prelude) Erlang (4.7.3) 162 pages (251 including builtin functions) Scheme (R5RS): 17 pages (45 including standard procedures) -- View this message in context: http://old.nabble.com/Language-simplicity-tp27134989p27137827.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
Re: [Haskell-cafe] Are functional dependencies around to stay?
Günther Schmidt wrote: I'm wondering if there is any chance that functional dependencies will not be around in the future. As was previously noted they are supposed to be replaced by type families, but for me the crucial difference between these two now is that currently type families do not allow overlapping instances at all while fundeps can be used with overlapping instances in GHC with -XOverlappingInstances flag.. Not sure how this difference is going to be changed in the future, but I am currently using fundeps because of it (I'd prefer type families otherwise). -- View this message in context: http://old.nabble.com/Are-functional-dependencies-around-to-stay--tp26873777p26889879.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
Re: [Haskell-cafe] Are functional dependencies around to stay?
Hi Stephen,
Stephen Tetley-2 wrote:
Currently this seems a more like a rumour than a fact - from [1] Type
Families and Fun Deps are equivalently expressive which seems a
worthwhile point to restate.
I've got the same impresion initially and was keen to use TF in favor to FD.
And I'm probably missing something here... but here is wiki example which, I
think, gives an example of the 'difference' I was refering to:
http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap (see '2 Notes and
variations', last part).
As an additional example I can point to Oleg Kiselyov's TypeCast
implementation (http://okmij.org/ftp/Haskell/deepest-functor.lhs), here is
its slightly modified version:
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
module FMAP where
data Atom
-- Check if a type is a collection type. This is the only typeclass that
-- needs overlapping instances
class IsCollection t coll | t - coll
instance IsCollection (m a) (m ())
instance Atom ~ coll = IsCollection t coll
-- The desired deep functor. Needs no overlapping instances
class Funct a b c1 c2 | c1 - a, c1 b - c2 where
f_map :: (a - b) - c1 - c2
instance (IsCollection c1 coll, Funct' coll a b c1 c2)
= Funct a b c1 c2 where
f_map = f_map' (undefined::coll)
class Funct' coll a b c1 c2 | coll c1 - a, coll c1 b - c2 where
f_map' :: coll - (a - b) - c1 - c2
instance Funct' Atom a b a b where
f_map' _ = id
instance (Functor m, Funct a b c d) = Funct' (m ()) a b (m c) (m d) where
f_map' _ = fmap . f_map
test1 = f_map (+1) [[[1::Int,2,3]]]
test2 = f_map not [[True], [False]]
test3 = f_map not (Just [Just True, Nothing])
test4 = f_map not (print here
return (Just (Just [Just [True], Nothing])))
= print
Still I am not sure how to rewrite this example using Type Families..
--
View this message in context:
http://old.nabble.com/Are-functional-dependencies-around-to-stay--tp26873777p26891353.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
Re: [Haskell-cafe] Help to solve simple problem !
Aneto wrote:
compress :: Eq a = [a] - [(a, Int)]
If you have string AAABCCC it transforms it to : {A, 3} {B,1} {C,3}
Basically you need to group equal elements of the list first and then
transform every group (which is a list of equal elements) to the tuple of
(first_element , the_ length_of_the_group). All necessary functions can be
found in Prelude and Data.List:
import Data.List
compress :: Eq a = [a] - [(a, Int)]
compress xs = map (\g - (head g, length g)) (group xs)
PS You can express it somehow nicer with arrows thought:
import Data.List
import Control.Arrow
compress :: Eq a = [a] - [(a, Int)]
compress = map (head length) group
--
View this message in context:
http://old.nabble.com/Help-to-solve-simple-problem-%21-tp26249028p26294356.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
Re: [Haskell-cafe] Observer pattern in Haskell?
Andy Gimblett-2 wrote: To help manage dependencies between state and UI elements, I looked for a Haskell version of the Observer design pattern Isn't Reactive Programming approach more suitable than Observer if we talk about Haskell? -- View this message in context: http://old.nabble.com/Observer-pattern-in-Haskell--tp26267269p26268135.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
Re: [Haskell-cafe] Observer pattern in Haskell?
Andy Gimblett-2 wrote: Possibly. Care to expand? If you have a more elegant solution, which fits in well with ordinary wxHaskell, I'd be interested. I believe there are a few experimental frameworks built on top of wxHaskell which use Functional Reactive Programming, like http://www.haskell.org/haskellwiki/Phooey Phooey . They seem to be more ellegant, but probably less practical for now since they are still experimental. I just thought that FRP is more suitable for Haskell but probably in case of wxHaskell it is not a case. Sorry if it was off topic. -- View this message in context: http://old.nabble.com/Observer-pattern-in-Haskell--tp26267269p26269564.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
Re: [Haskell-cafe] list - sublists
satorisanitarium wrote: How to make a list of sublists out of a list, whether they be a list of numbers or a string. Without recursion (with fold) starting from the tail of the input list: foo n = foldr st [[]] where st x xss | x == n = [x]:xss st x (xs:xss) = (x:xs):xss -- View this message in context: http://www.nabble.com/list--%3E-sublists-tp25975341p25998649.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
Re: [Haskell-cafe] convert a list of booleans into Word*
Bulat Ziganshin-2 wrote: sum . zipWith (*) (map (2^) [0..]) foldr1 $ \b - (+b) . (*2) -- View this message in context: http://www.nabble.com/convert-a-list-of-booleans-into-Word*-tp25677589p25686400.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
Re: [Haskell-cafe] river crossing puzzle
pat browne-2 wrote: Hi, Does anyone know where there are any Haskell implementations of the the River Crossing puzzle (AKA Farmer/Fox/Goose/Grain). Here is an implementation of the similar problem with good explanation (see PDF): http://web.engr.oregonstate.edu/~erwig/zurg/ It isn't quite Farmer/Fox but it is rather generic. -- View this message in context: http://www.nabble.com/river-crossing-puzzle-tp25651350p25690342.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
Re: [Haskell-cafe] Deepest polymorphic functor
Ryan Ingram wrote: The problem is this: instance Num a = Num [a] where ... test = deep_fmap (+1) [[[ 1, 2, 3 :: Int ]]] What (+1) should be used? (+1) :: Int - Int (+1) :: [Int] - [Int] (+1) :: [[Int]] - [[Int]] (+1) :: [[[Int]]] - [[[Int]]] They could all be type-correct, so the snippet is ambiguous. But why then the following snippet doesn't cause ambiguity: deep_fmap (++a) b // - ba deep_fmap (++a) [b] // - [ba] deep_fmap (++a) [[b]] // - [[ba]] -- View this message in context: http://www.nabble.com/Deepest-polymorphic-functor-tp24709303p24751663.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
Re: [Haskell-cafe] Deepest polymorphic functor
Ryan Ingram wrote: instance Num a = Num [a] where ... O... I see what you mean. So... no way around? e.g. no way to define deep_fmap for not grounded types? -- View this message in context: http://www.nabble.com/Deepest-polymorphic-functor-tp24709303p24752047.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
Re: [Haskell-cafe] Deepest polymorphic functor
Ryan Ingram wrote: What would this do with instance Num a = Num [a] in scope? It should work not only for Num a anyway (like normal Functor would do) but if you could give me an example, how exactly could I use Num a here... -- View this message in context: http://www.nabble.com/Deepest-polymorphic-functor-tp24709303p24748175.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
Re: [Haskell-cafe] Deepest polymorphic functor
PS In regards to the original http://okmij.org/ftp/Haskell/deepest-functor.lhs Am I right that the following code from the sample: class IsCollection t coll | t - coll instance IsCollection (m a) (m ()) instance TypeCast Atom coll = IsCollection t coll class TypeCast a b | a - b, b-a where typeCast :: a - b class TypeCast' t a b | t a - b, t b - a where typeCast' :: t-a-b class TypeCast'' t a b | t a - b, t b - a where typeCast'' :: t-a-b instance TypeCast' () a b = TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b = TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x may now be reduced to: class IsCollection t coll | t - coll instance IsCollection (m a) (m ()) instance (Atom ~ coll) = IsCollection t coll ? -- View this message in context: http://www.nabble.com/Deepest-polymorphic-functor-tp24709303p24748240.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] Deepest polymorphic functor
I was wondering if it is possible to somehow change deep f_map from http://okmij.org/ftp/Haskell/deepest-functor.lhs article in a such a way that it would work not only for monotypes like in the provided example: test1 = f_map (+1) [[[1::Int,2,3]]] But for polymorphic types as well (e.g. behaves like simple map) so the following line would compile as well: test1 = f_map (+1) [[[1,2,3]]] ? -- View this message in context: http://www.nabble.com/Deepest-polymorphic-functor-tp24709303p24709303.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
