FOP/ex8.6 - 大久保弘崇

ex8.21

highになっているビットの数を数えるためにbitAdderを並べる。

count1s bs = snd $ row (\(xs,b)->(undefined, fst $ bitAdder (b, xs))) (replicate (length bs) low, bs)
 
sameHs :: (Int->([Bit]->[Bit])->([Bit]->[Bit]))->Int->[Bit]->Bit
sameHs merge n inp = ok where
  (inpL, inpR) = halveList inp
  out = merge n twoBitSort inp
  ok = (sorted inpL <&> sorted (reverse inpR)) ==> (count1s inp <==> count1s out)
 
prop_sameHs :: (Int->([Bit]->[Bit])->([Bit]->[Bit]))->Int->Property
prop_sameHs merge n = forAll (list (2^n)) $ \ inp -> sameHs merge n inp
 

加算するレジスタ幅はbsの長さのlogで充分だが手を抜いた。

ex8.22

極端に無精をしてみる。

odds f = splitAt 1 ->- (id -|- odds1) ->- append where
  odds1 = reverse ->- splitAt 1 ->- (id -|- odds2) ->- append ->- reverse
  odds2 = reverse ->- evens f ->- reverse
 

コメント