Problem
I am working on a micro project: a Haskell DSL for describing circuits.
(You can find the code here)
I’m pretty happy with everything so far, but there is an ugly function alu32
:
alu32 c0 c1 c2 a b =
let aluc = alu1 c0 c1 c2
(out0, cout0) = aluc (a !! 0) (b !! 0) c0
(out1, cout1) = aluc (a !! 1) (b !! 1) cout0
(out2, cout2) = aluc (a !! 2) (b !! 2) cout1
(out3, cout3) = aluc (a !! 3) (b !! 3) cout2
...
Can anyone suggest a more idiomatic way of representing this? Also, if you feel like browsing the repository, feel free to make any suggestions. I have a bunch of things that I would still like to implement.
Solution
Can anyone suggest a more idiomatic way of representing this?
The equations for the ALU have the form
(out !! i, cout !! i) = aluc (a !! i) (b !! i) (cout !! (i  1))
so we should be able to express all of the equations with a single equation that manipulates lists. If only cout !! (i  1)
would be something !! i
, this would be easier because all the indexes would be uniform. We can make the indexes more uniform by defining cin = c0 : cout
, and then the equations become:
(out !! i, cout !! i) = aluc (a !! i) (b !! i) (cin !! i)
Now we can make a loop over i to implement alu32 as follows:
alu32 c0 c1 c2 a b =
let (out, cout) = unzip [alu1 c0 c1 c2 (a !! i) (b !! i) (cin !! i)  i < [0 .. 31]]
cin = c0 : cout
...
in ...
This should solve the main question: How to implement alu32 without repeating all these equations. On the way, I also replaced the translate with an unzip.
However, we can do even better if we avoid the index computations. There are two problems with the indices: Index lookup is slow and awkward compared to just looping over the elements of a list. And the loop over the indices forces us to choose a fixed upper bound in the [0 .. 31]
expression.
To avoid the indices, we note that the list comprehension
[alu1 c0 c1 c2 (a !! i) (b !! i) (cin !! i)  i < [0 .. 31]]
just loops over three lists in parallel, a
, b
and cin
. This parallel loop over three lists can be expressed with zipWith3 as follows:
unzip (zipWith3 (alu1 c0 c1 c2) a b cin)
Or you activate GHC’s extension for parallel list comprehensions by putting {# LANGUAGE ParallelListComp #}
near the top of the file, and then use:
unzip [alu1 c0 c1 c2 ai bi ci  ai < a  bi < b  ci < cin]
The latter will desugar to the former. Clearly, this variant of the code doesn’t use any indices anymore. This also means that it works for arbitrary bitvectors, not just 32bit ones. We only have to adapt the rest of the alu32 implementation to avoid indices, too. For example:
alu :: Wire  Control Bit 0
> Wire  Control Bit 1
> Wire  Control Bit 2
> ByteWire  n Bit Wire addend
> ByteWire  n Bit Wire addend
> (ByteWire, Wire, Wire, Wire)
alu c0 c1 c2 a b =
let (out, cout) = unzip (zipWith3 (alu1 c0 c1 c2) a b cin)
cin = c0 : cout
overflow = xorGate (take 2 (reverse cout))
isZero = map (all (==False)) out
negative = last out
in (out, overflow, isZero, negative)
This version of alu is concise and works for bitvectors of arbitrary length.
I’m not really sure about map (all (== False)) out
to compute that all bits are zero. Maybe I would use something like map (all not) out
or map (not . or) out
. Note sure. Or maybe I would define a gate for deciding that something is all zeros and then use that one.
Also, if you feel like browsing the repository, feel free to make any suggestions.

Consider adding a cabal file. When I cloned your repo in order to test the above suggestion, I was confused that
cabal sandbox init && cabal build
didn’t work. You can just runcabal init
in the repository and it should ask you questions to help you make the cabal file. 
Consider making the
Wire
type more abstract.Currently, you have:
type Wire = [Binary]  A list of discrete states
Instead, you could use:
newtype Wire = Secret [Binary]
The benefit of this definition is that it becomes harder to “cheat” and use list operations instead of gates. Later, when you are finished defining the basic gates, you can make a module that exports the
Wire
type and the gates, but not theSecret
constructors. This way, you force the users of that module to use the gates and only the gates to compose wires.