$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2008/03/20

### Modelling Digital Logic in Haskell

scm 老師這次出的 Haskell 練習題是用 Haskell 寫 digital logic components。這正是 OUCL 大學部教 digital logic 的方式，真是太浪漫了 XD。一條接線是以一個 list 表示，其中每個元素是那條線在各個離散時間點的訊號值。

type Wire = [Bool]

type TimeSlice = [Bool]

binary :: Int -> Integer -> TimeSlice
binary c = take c . map ((/= 0) . (mod 2)) . iterate (div 2)


numeric :: Int -> TimeSlice -> Integer
numeric c = sum . tri (*2) . map bit2num . take c

tri f（就是出現在 Horner's rule 裡面的那個函式）和 bit2num 的定義是：
tri f = foldr (\x xs -> x : map f xs) []
bit2num False = 0
bit2num True  = 1


constant :: Int -> Integer -> [Wire]
constant c = map repeat . binary c


add :: Int -> TimeSlice -> TimeSlice -> TimeSlice
add c = curry (binary (c + 1) . uncurry (+) . parallel (numeric c))

add c 把它收到的兩個 time slices 轉為數值加起來，然後轉換回長度 c + 1 的 time slice，多一位是最高位的進位。這其實是加法電路的 specification，以後我希望能從這裡導出 ripple adder, carry look-ahead adder 等等的。(Hope it's possible. XD)

adder :: Int -> [Wire] -> [Wire] -> [Wire]

[Wire] 是一條一條的線，但 add c 處理的是一個一個的 time slice，我們必須寫個函式在這兩個觀點間轉換。稍微想一想就會發覺，這其實就是 matrix transposition，所以我們可以寫
transpose = foldr (zipWith (:)) (repeat [])


adder c = curry (transpose . uncurry (zipWith (add c)) . parallel transpose)


split f g a = (f a, g a)
cross f g = split (f . fst) (g . snd)
parallel f = cross f f


map head (adder 5 (constant 5 7) (constant 5 8))


wirewise :: [TimeSlice] -> [Wire]
wirewise = unfoldr f
where f ([] : xss) = Nothing
f xss        = (Just . split (map head) (map tail)) xss


unfoldr f a = case f a of
Nothing -> []
Just (x, b) -> x : unfoldr f b


timewise :: [Wire] -> [TimeSlice]
timewise = foldr (zipWith (:)) (repeat [])

adder 於是就變成
adder :: Int -> [Wire] -> [Wire] -> [Wire]
adder c = curry (wirewise . uncurry (zipWith (add c)) . parallel timewise)


*Main> map head (adder 5 (constant 5 7) (constant 5 8))
[True,True,True,True,False,False]


--

Labels:

scm3/21/2008 3:41 am 說：

Josh Ko3/21/2008 4:27 am 說：

--

Anonymous3/21/2008 5:05 am 說：

Josh Ko3/21/2008 5:34 am 說：