I wrote a small article around implementing Cartesian products, starting from Haskell’s sequence. The article goes through a naive Haskell implementation, a more idiomatic list-comprehension version, native sequence, then versions using Data.Vector.Unboxed, mutable vectors, runST, unsafeFreeze to try a different memory representation. The second half compares those designs with C implementations, mostly to look at what changes when the memory layout and allocation model are made explicit. The most interesting result for me was that changing representation in Haskell reduced allocations a lot without automatically improving runtime. In some cases, fusion helped a bit (no temporary indices). I’d be happy to get feedback on the Haskell side, especially the vector/ST implementations and whether there are more idiomatic or faster ways to express this. Here is the article link: https://julienlargetpiet.tech/articles/the-cartesian-product-disaster-tour-haskell-c-and-25gb-of-allocations.html If you want to share any optimizations, you can do a PR at this repo: https://github.com/julienlargetpiet/PerfLabs It will be mentioned in the next article update. PS: We now managed to find (currently) best version which is this one (in C) running at 160ms for 100k iterations to 55 lists here: https://github.com/julienlargetpiet/PerfLabs/blob/main/CartesianProduct/contrib2/contrib2.c I'm updating after trying some new Haskell impl, thanks everyone for the help and the intuition on where to dig !

So I have some time off and I'm relearning Haskell, and part of the charm was coming back to cute recursive, lazy, infinite definitions like this: fibSequence :: [Integer] fibSequence = 0 : 1 : zipWith (+) fibSequence (tail fibSequence) which is a pretty good way to define the Fibonacci sequence. And then I was looking around and watching this video, which is really fun, which gives primeSequence :: [Integer] primeSequence = sieveOfEratosthenes [2..] sieveOfEratosthenes :: [Integer] -> [Integer] sieveOfEratosthenes (p:ps) = p : sieveOfEratosthenes [ x | x <- ps, x `mod` p /= 0] And I was like OMG GENIUS! Nice. And then later I tried using this to solve problems in Project Euler, and realized quickly that this indeed is NOT the proper sieve of Erastosthenes, because it does multiple cancellations for each number. So I had to go down a rabbit hole, which has shown me that truly lazy infinite structures are VERY HARD TO WRITE.

Hi, I'm learning Haskell, and I admit I'm just playing with it right now. While I'm not a terribly experienced programmer, I do have a Bachelor's in Computer Science. My professional experience has been restricted to mostly web development in Typescript sadly. I have not touched functional programming, but this seems unrelated to functional intricacies and more me having a primitive understanding of number types. I'm playing with pattern matching and guards so maybe excuse the silly code, I'm just starting. I try loading (":l haskell_test.hs") my file in GHCi and get the following compile error "Could not deduce ‘RealFrac a’ arising from a use of ‘floor’ from the context: Num a" . I take in type Num, and floor doesn't like that general of a type, I take it? -- testing pattern matching and guards isXFactorOfY :: Num a => a -> a -> Bool isXFactorOfY 0 0 = True isXFactorOfY 0 y = False isXFactorOfY x 0 = False isXFactorOfY 1 1 = True isXFactorOfY 1 y = False isXFactorOfY x 1 = False isXFactorOfY x y | x > y = False | abs(x / y) > floor( abs(x)/abs(y) ) = False | otherwise = True I've tried replacing Num a with Real a, RealFrac a, and some other things I've seen. But I'm just poking blindly and don't actually understand the exact issue. I'd like some help understanding it explicitly rather than stumbling upon the compile-able code. I see the reference for floor is here: https://hackage.haskell.org/package/ClassyPrelude-0.1/docs/Prelude-Math.html#v:floor I guess I'm confused what it want's floor to take in, I figured any number that's an Int or Float would work. But I'm not sure how to define that the way it wants. Again sorry for the silly code. I am quite rusty and am having a rough time getting back into .... problem solving, and reading APIs and references it seems. Thank you in advance for any help or direction you give. The full compile error output is as follows: ghci> :l haskell_test.hs [1 of 2] Compiling Main ( haskell_test.hs, interpreted ) haskell_test.hs:3:14: error: [GHC-39999] • Could not deduce ‘Eq a’ arising from the literal ‘0’ from the context: Num a bound by the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool at haskell_test.hs:2:1-39 Possible fix: add (Eq a) to the context of the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool • In the pattern: 0 In an equation for ‘isXFactorOfY’: isXFactorOfY 0 0 = True | 3 | isXFactorOfY 0 0 = True | ^ haskell_test.hs:9:29: error: [GHC-39999] • Could not deduce ‘Ord a’ arising from a use of ‘>’ from the context: Num a bound by the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool at haskell_test.hs:2:1-39 Possible fix: add (Ord a) to the context of the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool • In the expression: x > y In a stmt of a pattern guard for an equation for ‘isXFactorOfY’: x > y In an equation for ‘isXFactorOfY’: isXFactorOfY x y | x > y = False | abs (x / y) > floor (abs (x) / abs (y)) = False | otherwise = True | 9 | isXFactorOfY x y | x > y = False | ^ haskell_test.hs:10:33: error: [GHC-39999] • Could not deduce ‘Fractional a’ arising from a use of ‘/’ from the context: Num a bound by the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool at haskell_test.hs:2:1-39 Possible fix: add (Fractional a) to the context of the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool • In the first argument of ‘abs’, namely ‘(x / y)’ In the first argument of ‘(>)’, namely ‘abs (x / y)’ In the expression: abs (x / y) > floor (abs (x) / abs (y)) | 10 | | abs(x / y) > floor( abs(x)/abs(y) ) = False | ^ haskell_test.hs:10:40: error: [GHC-39999] • Could not deduce ‘RealFrac a’ arising from a use of ‘floor’ from the context: Num a bound by the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool at haskell_test.hs:2:1-39 Possible fix: add (RealFrac a) to the context of the type signature for: isXFactorOfY :: forall a. Num a => a -> a -> Bool • In the second argument of ‘(>)’, namely ‘floor (abs (x) / abs (y))’ In the expression: abs (x / y) > floor (abs (x) / abs (y)) In a stmt of a pattern guard for an equation for ‘isXFactorOfY’: abs (x / y) > floor (abs (x) / abs (y)) | 10 | | abs(x / y) > floor( abs(x)/abs(y) ) = False | ^^^^^ Failed, unloaded all modules.