How to do nested 'looping' in Haskell-CodePudding

I am looking at some JAVA code and I would like to know how this can be translated into Haskell.


IntStream.range(0, cookedWords.length).parallel().forEach((int i) -> {
  int A = cookedWords[i];

  for (int j = i   1; j < cookedWords.length;   j) {
      int B = cookedWords[j];
      if ((A & B) != 0) continue;
      int AB = A | B;

      for (int k = j   1; k < cookedWords.length;   k) {
          int C = cookedWords[k];
          if ((AB & C) != 0) continue;
          int ABC = AB | C;

          for (int l = k   1; l < cookedWords.length;   l) {
              int D = cookedWords[l];
              if ((ABC & D) != 0) continue;
              int ABCD = ABC | D;

              for (int m = l   1; m < cookedWords.length;   m) {
                  int E = cookedWords[m];
                  if ((ABCD & E) != 0) continue;

                  System.out.printf("%s\n%s\n\n",
                          stopwatch.elapsedTime(),
                          decodeWords(A, B, C, D, E));
              }
          }
      }
  }
});

This code is taken from here

I am guessing that there are a few things that need to be done here. unboxed vectors, run parallel etc. but I don't even know how to start with the indexing the way it is done in the imperative code. Or is this where people start to tell me to stay away from Haskell?

What is a literal translation of this code? And is there a better 'Haskell' way of doing something like this?

This is all I can think of doing. But it is obviously inefficient.

[ (a,b,c,d,e) 
  | a <- cookedWords, b <- cookedWords, c <- cookedWords, d <- cookedWords, e <- cookedWords
  , foldl1' (.|.) [a,b,c,d,e] == 0
  ]

CodePudding user response：

One could do a pretty literal translation if one were so inclined, but so much work with indices is usually a sign of a failure to understand the real iteration pattern. Here, the most straightforward translation I see is to maintain A, B, C, and so on, and also keep track of the remainder of the list. A monad comprehension using tails to break the lists apart seems simple enough. I imagine something like this:

import Data.Bits
import Data.List (tails)
import Data.Maybe (listToMaybe)
import Control.Monad (guard)

cookedWords :: [Int]
cookedWords = [0..]

match :: [Int] -> Maybe (Int, Int, Int, Int, Int)
match words =
  listToMaybe $ do
    a : as <- tails cookedWords
    b : bs <- tails as
    guard $ a .&. b == 0
    let ab = a .|. b
    c : cs <- tails bs
    guard $ ab .&. c == 0
    let abc = ab .|. c
    d : ds <- tails cs
    guard $ abc .&. d == 0
    let abcd = abc .|. d
    e : es <- tails ds
    guard $ abcd .&. e == 0
    pure (a, b, c, d, e)

Here of course since I've defined words to be [0..], it just finds the first 5 powers of 2 (well okay, 4 of them and a zero):

*Main> match cookedWords
Just (0,1,2,4,8)

But it would be better to generalize this to a function whose input is the list of matching words to search as well as the desired group size, and whose output is a list of such matches.

match :: Int -> [Int] -> [[Int]]
match = go 0
  where go mask 0 _ = [[]]
        go mask n words = do
          x : xs <- tails words
          guard $ mask .&. x == 0
          let mask' = mask .|. x
          (x:) <$> go mask' (n - 1) xs

This way, we don't have to worry about specific named variables for our five intermediate states or the result, we can just work on a list of arbitrary size. And as a bonus, we can get multiple results if we like:

*Main> take 5 $ match 5 cookedWords
[[0,1,2,4,8],[0,1,2,4,16],[0,1,2,4,24],[0,1,2,4,32],[0,1,2,4,40]]

Finding a reasonable abstraction has let us write code that is much simpler and more obviously correct than the Java version.

CodePudding user response：

You can interleave filtering and enumerating, just like in the imperative code:

[ (a,b,c,d,e) 
  | a <- cookedWords
  , b <- cookedWords
  , a .&. b == 0
  , let ab = a .|. b
  , c <- cookedWords
  , ab .&. c == 0
  , let abc = ab .|. c
  , d <- cookedWords
  , abc .&. d == 0
  , let abcd = abc .|. d
  , e <- cookedWords
  , abcd .&. e == 0
]

This will however still yield symmetrical results: indeed, it can pick a = 2 and b = 4, but also a = 4 and b = 2. We can use tails :: [a] -> [[a]] to prevent this with:

import Data.List(tails)

[ (a,b,c,d,e) 
  | (a:as) <- tails cookedWords
  , (b:bs) <- tails as
  , a .&. b == 0
  , let ab = a .|. b
  , (c:cs) <- tails bs
  , ab .&. c == 0
  , let abc = ab .|. c
  , (d:ds) <- tails cs
  , abc .&. d == 0
  , let abcd = abc .|. d
  , e <- ds
  , abcd .&. e == 0
]