Some kind of iteration

Question

Sorry if the title is bad...

So my problem is that i got this code:

asd (a:as) (b:bs)= tail(rox(tail(rox (tail (rox (a:as) (b:bs))) (b:bs))) (b:bs))
rox [] as = as
rox as [] = as
rox (a:as) (b:bs) = map abs (a-b:rox as bs)

my type must be: asd :: [Int]->[Int]->[Int]

I spent my half day figuring out a good solution, but I just cant think on one, so I would be very happy if someone could help me. I want to subtract from the (a:as)list the (b:bs)list and after this I want to delete the first number and do it again with the result(result-(b:bs)), until I get a (length (b:bs))-1) list. And if the (a:as)/result is lower than the (b:bs), for exapmle: 00101<10011 I need to change all (b:bs) numbers to 0(and if the result is higher again keep using the (b:bs)). The exapmle is working fine with the code above, but I want to use it with any list. Maybe I need to use the iterate function but I wasnt able to figure out how.

Here is an example:

11010(a:as)
101(b:bs)
01110(result)
 1110(after using tail)
 101(b:bs again)
 0100(result)
  100(after tail)
  101(b:bs)
  001(result)
   01(final result after using tail, so its 1number shorter than the (b:bs) list

Thank you so much for your help!

edit: With this I can check which binary number is higher, so with this I can turn all bs number into 0, but i dont know how to implement it.

(%>=%) :: [Int] -> [Int] -> Bool
(%>=%) [] [] = True
(%>=%) as [] = True
(%>=%) [] bs = False
(%>=%) as bs
    | filter (/=0) (takeWhile (>(-1))(ro as bs))==[]=False
    | elem 1 (takeWhile (>(-1))(ro as bs))==True=True

ro :: [Int] -> [Int] -> [Int]
ro []       bs       = bs
ro as       []       = as
ro (a:as) (b:bs) = (2*a) - b: ro as bs

Result:

asd [1,1,1,0,0,1,0,1,0,0,0,0] [1,1,0,1,1]
asd [0,1,1,1,1,0,1,0,0,0,0] [1,1,0,1,1]
asd [1,1,1,1,0,1,0,0,0,0] [1,1,0,1,1]
asd [0,1,0,1,1,0,0,0,0] [1,1,0,1,1]
asd [1,0,1,1,0,0,0,0] [1,1,0,1,1]
asd [0,1,1,0,0,0,0] [1,1,0,1,1] < here is something wrong because its: 1,1,0,1,0,0,0 and from here everything is wrong
asd [1,1,0,0,0,0] [1,1,0,1,1]
asd [1,0,0,0,0] [1,1,0,1,1]
asd [0,0,0,0] [1,1,0,1,1]
[0,0,0,0]

Answer 1

It seems like you're trying to implement the remainder rem (similar to modulo mod) function but for binary lists. It is much faster if you convert the list to an Integer and perform rem on it.

First, a function that converts from binary to an Integer:

unbinary :: [Int] -> Integer
unbinary = foldl (\ a b -> a * 2 + fromIntegral b) 0

Then, a function that converts an Integer into binary:

binary :: Integer -> [Int]
binary = reverse . go
  where
    go 0 = []
    go d =
      let (q, r) = quotRem d 2
      in fromIntegral r : binary q

Finally, a function that handles rem for binary lists:

remBinary :: [Int] -> [Int] -> [Int]
remBinary a b = binary $ inta `rem` intb
  where
    inta = unbinary a
    intb = unbinary b

The "beauty" of this solution is that you can replace the 2's with any number (3, 6, 13 etc) and it will work for any base - not just binary.

---

To answer your original question:

This is a very strange function indeed, and I would not use iterate for it.

asd :: [Int] -> [Int] -> [Int]
-- If there is nothing to subtract, let's assume that we should return as
asd as [] = as
asd as bs
  -- If the length of `as` is shorter than `bs`, we are done.
  | length as < length bs
  = as
  | head as == 0
  = asd (tail as) bs
  -- Otherwise, compute `rox as bs`, take its `tail`, and call `asd` recursively
  | otherwise
  = asd (tail (rox as bs)) bs

-- I simplified your version of this function a bit
rox :: [Int] -> [Int] -> [Int]
rox []       bs       = bs
rox as       []       = as
rox (a : as) (b : bs) = abs (a - b) : rox as bs

The last part of asd could also be written like this:

  = let diff = rox as bs
        tailOfDiff = tail diff
    in asd tailOfDiff bs

That way, it follows your description more closely.