Iterating a dovetail over endless lists in Haskell

Question

I want to iterate 2 (or 3) infinite lists and find the “smallest” pair that satisfies the condition, for example:

until pred [(a,b,c) | a<-as, b<-bs, c<-cs] where pred (a,b,c) = a*a + b*b == c*c as = [1..] bs = [1..] cs = [1..] 

The above will not be very far, like a == b == 1 throughout the program launch. Is there a good way to solve the problem, for example. construct an infinite sequence [(1,1,1),(1,2,1),(2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),..] ?

Bonus: is it possible to generalize to n-tuples?

Answer 1

There is a monad, Omega .

 Prelude> let as = each [1..] Prelude> let x = liftA3 (,,) as as as Prelude> let x' = mfilter (\(a,b,c) -> a*a + b*b == c*c) x Prelude> take 10 $ runOmega x' [(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(8,15,17),(15,8,17)] 

Using its applicative functions, you can generalize to arbitrary tuples:

 quadrupels = (,,,) <$> as <*> as <*> as <*> as -- or call it liftA4 

But : this in itself does not eliminate duplication, of course. This gives you the correct diagonalization. Perhaps you could use monad assrehensions with an approach similar to Thomas, or just another mfilter pass (limitation in this case b /= c ).

Answer 2

List of concepts - excellent (and short) ways to solve such problems. Firstly, you know that you want all combinations (a,b,c) to satisfy a^2 + b^2 = c^2 - it is useful to note that (considering only positive numbers) a <= c && b <= c .

To generate our list of candidates, we can say that c varies from 1 to infinity, and a and b from one to c .

 [(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c]] 

To get to the solution, we just need to add your required equation as a guard:

 [(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c], a*a+b*b == c*c] 

This is inefficient, but the result is correct:

 [(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15)... 

There are more fundamental methods than blind testing, which can solve this problem.

Answer 3

{- It depends on what is the "smallest". But here is the solution for the concept of "least" if tuples were compared first to their max. number, and then by their total amount. (You can simply copy and paste my entire answer into a file when I write the text in the comments.)

We will need a nub later. -}

 import Data.List (nub) 

{- just to illustrate: a simple case with 2 tuples. -}

 -- all the two-tuples where 'snd' is 'n' tuples n = [(i, n) | i <- [1..n]] -- all the two-tuples where 'snd' is in '1..n' tuplesUpTo n = concat [tuples i | i <- [1..n]] 

{- To get all the results, you will need to insert a flip of each tuple into the stream. But do it later and generalize first.

Building tuples of arbitrary length is somewhat complicated, so we will work on lists. I call them "kList" if they have a length of "k". -}

 -- just copied from the tuples case, only we need a base case for k=1 and -- we can combine all results utilizing the list monad. kLists 1 n = [[n]] kLists kn = do rest <- kLists (k-1) n add <- [1..head rest] return (add:rest) -- same as above. all the klists with length k and max number of n kListsUpTo kn = concat [kLists ki | i <- [1..n]] -- we can do that unbounded as well, creating an infinite list. kListsInf k = concat [kLists ki | i <- [1..]] 

{- The next step is to rotate these lists, because so far the largest number is always in last place. Therefore, we just look at all the turns to get all the results. Using nub here is admittedly inconvenient, you can improve it. But without this, lists in which all elements are the same repeat k times. -}

 rotate nl = let (init, end) = splitAt nl in end ++ init rotations kl = nub [rotate il | i <- [0..k-1]] rotatedKListsInf k = concatMap (rotations k) $ kListsInf k 

{- It remains to convert these lists into tuples. This is a bit inconvenient because each n-tuple is a separate type. But it is simple, of course. -}

 kListToTuple2 [x,y] = (x,y) kListToTuple3 [x,y,z] = (x,y,z) kListToTuple4 [x,y,z,t] = (x,y,z,t) kListToTuple5 [x,y,z,t,u] = (x,y,z,t,u) kListToTuple6 [x,y,z,t,u,v] = (x,y,z,t,u,v) 

{- Some tests:

 *Main> take 30 . map kListToTuple2 $ rotatedKListsInf 2 [(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3),(1,4),(4,1),(2,4),(4,2),(3,4), (4,3),(4,4),(1,5),(5,1),(2,5),(5,2),(3,5),(5,3),(4,5),(5,4),(5,5),(1,6),(6,1), (2,6), (6,2), (3,6)] *Main> take 30 . map kListToTuple3 $ rotatedKListsInf 3 [(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,2,1),(2,1,2),(2,2,2),(1,1,3),(1,3,1), (3,1,1),(1,2,3),(2,3,1),(3,1,2),(2,2,3),(2,3,2),(3,2,2),(1,3,3),(3,3,1),(3,1,3), (2,3,3),(3,3,2),(3,2,3),(3,3,3),(1,1,4),(1,4,1),(4,1,1),(1,2,4),(2,4,1),(4,1,2)] 

Edit: I realized that there is a mistake: just turning the ordered lists, of course, is not enough. The solution should be somewhere close to what

 rest <- concat . map (rotations (k-1)) $ kLists (k-1) n 

in kLists , but then there are some problems with repetitive exits. I suppose you can figure it out. ;-) -}

Answer 4

This answer is for a more general problem for an unknown predicate. If the predicate is known, more effective solutions are possible, like others that listed solutions based on knowledge that you do not need to iterate for all Ints for a given c.

When you work with endless lists, you need to do a width search for the first time. Understanding the list gives only a search by depth, so you never reach a solution in your source code.

 counters 0 xs = [[]] counters n xs = concat $ foldr f [] gens where gens = [[x:t | t <- counters (n-1) xs] | x <- xs] f ys n = cat ys ([]:n) cat (y:ys) (x:xs) = (y:x): cat ys xs cat [] xs = xs cat xs [] = [xs] main = print $ take 10 $ filter p $ counters 3 [1..] where p [a,b,c] = a*a + b*b == c*c 

counters generates all possible counters for values ​​from a specified range of digits, including an infinite range.

First, we get a list of generators of valid meter combinations - for each allowed digit, combine it with all the valid combinations for smaller meters. This can lead to a generator that creates an infinite number of combinations. Thus, we need to borrow from each generator evenly.

So gens is a list of generators. Think of it as a list of all counters starting with one digit: gens !! 0 gens !! 0 - a list of all counters starting with 1 , gens !! 1 gens !! 1 - a list of all counters starting with 2 , etc.

To borrow evenly from each generator, we could transfer the list of generators - this way we get a list of the first elements of generators, followed by a list of second elements of generators, etc.

Since the list of generators can be infinite, we cannot allow the list of generators to be transposed, because we will never be able to look at the second element of any generator (for an infinite number of digits we will have an infinite number of generators). So, we list the elements from the generators "diagonally" - we take the first element from the first generator; then take the second element from the first generator and the first from the second generator; then we take the third element from the first generator, the second from the second and the first element from the third generator, etc. This can be done by folding the generator list using the function f , which zips up two lists - one list is a generator, the other - generators already zipped - the beginning of one of them shifts one step, adding []: to the head. It's almost zipWith (:) ys ([]:n) - the difference is that if n or ys is shorter than the other, we do not leave the rest of the other list. Note that bending with zipWith (:) ys n will transpose.

Answer 5

For this answer, I will take the “smallest” to refer to the sum of the numbers in the tuple.

To list all possible pairs in order, you can first list all pairs with a sum of 2, then all pairs with a sum of 3, etc. In code

 pairsWithSum n = [(i, ni) | i <- [1..n-1]] xs = concatMap pairsWithSum [2..] 

Haskell does not have tools for working with n-tuples without using the Haskell template, so to generalize it you will have to switch to lists.

 ntuplesWithSum 1 s = [[s]] ntuplesWithSum ns = concatMap (\i -> map (i:) (ntuplesWithSum (n-1) (si))) [1..s-n+1] nums n = concatMap (ntuplesWithSum n) [n..] 

Answer 6

Here's a different solution, perhaps with a different, slightly different “smallest” idea. My order is just "all tuples with a maximum element N that appears in front of all tuples with a maximum element N + 1". I wrote versions for pairs and triples:

 gen2_step :: Int -> [(Int, Int)] gen2_step s = [(x, y) | x <- [1..s], y <- [1..s], (x == s || y == s)] gen2 :: Int -> [(Int, Int)] gen2 n = concatMap gen2_step [1..n] gen2inf :: [(Int, Int)] gen2inf = concatMap gen2_step [1..] gen3_step :: Int -> [(Int, Int, Int)] gen3_step s = [(x, y, z) | x <- [1..s], y <- [1..s], z <- [1..s], (x == s || y == s || z == s)] gen3 :: Int -> [(Int, Int, Int)] gen3 n = concatMap gen3_step [1..n] gen3inf :: [(Int, Int, Int)] gen3inf = concatMap gen3_step [1..] 

You cannot generalize it to N-tuples, although as long as you remain homogeneous, you can generalize it if you use arrays. But I do not want to tie my brain to this node.

Answer 7

It really depends on what you mean by “smallest”, but I assume that you want to find a tuple of numbers by its maximum element - therefore (2,2) less than (1,3) (while the standard Haskell ordering is lexicographical).

There is a data-ordlist package that is aimed specifically at working with ordered lists. The mergeAll (and mergeAllBy ) mergeAllBy allows you to combine a two-dimensional matrix, ordered in each direction, into an ordered list.

First, create the desired comparison function in the tuples:

 import Data.List (find) import Data.List.Ordered compare2 :: (Ord a) => (a, a) -> (a, a) -> Ordering compare2 xy = compare (max2 x, x) (max2 y, y) where max2 :: Ord a => (a, a) -> a max2 (x, y) = max xy 

Then, using mergeAll , we create a function that takes a comparator, a union function (which should be monotonic in both arguments), and two sorted lists. It combines all the possible elements from two lists using a function and creates a list of sorted results:

 mergeWith :: (b -> b -> Ordering) -> (a -> a -> b) -> [a] -> [a] -> [b] mergeWith cmp f xs ys = mergeAllBy cmp $ map (\x -> map (fx) xs) ys 

Using this function is very easy to create tuples ordered to the maximum:

 incPairs :: [(Int,Int)] incPairs = mergeWith compare2 (,) [1..] [1..] 

His first 10 elements:

 > take 10 incPairs [(1,1),(1,2),(2,1),(2,2),(1,3),(2,3),(3,1),(3,2),(3,3),(1,4)] 

and when we (for example) look for the first pair whose sum of squares is 65:

 find (\(x,y) -> x^2+y^2 == 65) incPairs 

we get the correct result (4,7) (unlike (1,8) if lexicographic ordering was used).

Answer 8

I think this is the simplest solution if the "smallest" is defined as x + y + z, because after you find your first solution in the space of triangles with a triangular triangle, your next solutions from the infinite list are bigger.

take 1 [(x,y,z) | y <- [1..], x <- [1..y], z <- [1..x], z*z + x*x == y*y] take 1 [(x,y,z) | y <- [1..], x <- [1..y], z <- [1..x], z*z + x*x == y*y] -> [(4,5, 3)]

It has the good property that it returns each symmetrically unique solution only once. x and z are also infinite, since y is infinite.

This does not work because the sequence for x never ends, and therefore you will never get the value for y, not to mention z. The rightmost generator is the innermost cycle.

take 1 [(z,y,x)|z <- [1..],y <- [1..],x <- [1..],x*x + y*y == z*z]

Answer 9

Sry, it's been a while since I made a haskell, so I'm going to put it in words.

As I noted in my comment. It is not possible to find the smallest in an infinite list, since there can always be less.

What you can do is use a streaming approach that takes lists and returns a list with only "valid" elements, i.e. e. where the condition is satisfied. Lets call this function triangle

You can to some extent calculate the list of triangles using take n (triangle ...) and from this element n you can find minium.