1

I have some code (generating the Rijndael S-box, for fun) that looks like this:

q0 = q  ⊕  shiftL q  1
q1 = q0 ⊕  shiftL q0 2
q2 = q1 ⊕  shiftL q1 4

It seems kind of silly - wouldn't it be the perfect situation for a fold? But I can't use a fold because shiftL requires an Int for the distance to shift, and of course xor requires Bits.

It seems awkward to me that a function meant to operate on Bits won't accept Bits for all its arguments. I'd be curious to hear the rational for that, but I'm more eager to know if there's any elegant way to achieve the fold I want.

9
  • What is the result you are looking for? Only q2, or all qis? May 8, 2017 at 18:19
  • I only require q2.
    – sacheie
    May 8, 2017 at 18:20
  • 3
    I’m not sure I understand what the problem is from the code you posted. Are you trying to use something other than 1, 2, 4 as the shift amount? Because what you wrote can be translated as a simple left fold, no? sbox q = foldl' (\ q' i -> q' `xor` shiftL q' i) q [1, 2, 4]
    – Jon Purdy
    May 8, 2017 at 18:20
  • 1
    The Bits typeclass represents bitvectors with bitwise operations. Instances of Bits are not necessarily meant to be interpreted as integers. On the other hand, Int is very common as a type of indices of a vector. Hence, shiftL accepts an Int.
    – Li-yao Xia
    May 8, 2017 at 18:25
  • 1
    @sacheie: The problem with xor . shiftL isn’t the mismatch between Bits a => a and Int, but rather the fact that it’s not implicitly lifted over multiple arguments; to get the behaviour of \ q -> xor q . shiftL q point-free, you could use the (a ->) applicative to write liftA2 (.) xor shiftL, or arrows to write xor &&& shiftL >>> uncurry (.), but neither is very readable.
    – Jon Purdy
    May 8, 2017 at 21:24

2 Answers 2

3

foldl :: (b -> a -> b) -> b -> [a] -> b iteratively applies a function starting with a b to a list of as until the list is exhausted and then returns the result. In this case our as can be the shift lengths. So 1, 2, 4. We can construct such a list with iterate :: (a -> a) -> a -> [a]. Indeed:

powers2 = iterate (2*) 1

Now we can feed that list to foldl. The function foldl performs is \qi s -> xor qi (shiftL qi s). So the complete function would be:

qn :: (Num a, Foldable t, Bits [a]) => Int -> r -> t Int -> [a]
qn n q = foldl (\qi s -> xor qi (shiftL qi s)) q $ take n $ iterate (2*) 1

So if we call qn 3 q we perform the function three times on q and thus obtain the q2 in your example. For example:

Prelude Data.Bits> qn 3 15
1285

Since:

q           = 0000 0000 1111
shiftL q  1 = 0000 0001 1110
              --------------
q0          = 0000 0001 0001
shiftL q0 2 = 0000 0100 0100
              --------------
q1          = 0000 0101 0101
shiftL q1 4 = 0101 0101 0000
              --------------
q2          = 0101 0000 0101

which is the binary equivalent of 1285.

0

Jon Purdy inferred what I should have stated clearly - I wanted a point-free function to pass to fold, and he provided one: liftA2 (.) xor shiftL.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.