Functional Programming: This thread is like a burrito

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Functional Programming: This thread is like a burrito

205b: Mar 25, 2007

Haskell question for you guys - I'm trying to build a cyclic data structure by "tying the knot", and my code compiles but then just hangs when I try to run it.

First, some context. I'm trying to build a doubly-linked binary tree. Each node in the tree references a state of a hash function, and non-root nodes include a block of input bytes such that hashing the input (starting from the node's state) yields the parent node's state.

It doesn't matter what the actual hash states are, only that this relationship between states holds. As a result, it's much easier to build the tree from the leaves up than from the root down. (Given two states, we can search for inputs that will produce a collision on any parent state, but if we start from the root, we have to search for states and inputs that yield the parent state.)

Here's the code:

(edit: more concise example below)

Sorry for the messiness! I'm still picking up the language and I think I'm probably overdoing it on pattern matching.

205b fucked around with this message at 23:03 on Jun 5, 2017

# ¿ Jun 5, 2017 10:12

Adbot: ADBOT LOVES YOU

# ¿ Apr 29, 2024 06:25

205b: Mar 25, 2007

dirby posted:

chunksOf 2 returns a list of lists of length 2 except maybe there could be a list of length 1 at the end if you didn't statically know that the argument had even length. Therefore, the best you could do is make it into a function that returns a list of pairs and does something counterintuitive at the end for odd-length inputs.

Right, if I run out of elements I get a final list of length 1 and then pattern matching fails at runtime. Even if chunksOf gave me tuples, the compiler wouldn't be able to guarantee me an input list of even length. I couldn't think of an unobtrusive way around that.

gonadic io posted:

Your pattern matching is mostly fine, although honestly given that the chunksOf 2 is hard-coded to be 2 I recommend getting it to just return a pair. Lists with statically-known lengths are a code smell.

In terms of your problem it's pretty difficult to know exactly where the problem is, could you post a smaller snippet that still demonstrates the bug please?

Also the Debug.Trace module is handy for this kind of thing, although you might have to be careful that you don't fully evaluate the entire tree when printing at each step, or you'll just move your problem to there.

That's already a huge help because I didn't know about Debug.Trace - I'd been putting conditional error calls in for debugging :haw:

I cut out all the hash stuff, so now nodes just have an integer value, and parent values are the sum of child values. I also cut the number of leaves to two, so it should be a three-node tree.

code:

data Node = Node Integer Relationships
data Relationships = Root Children | Branch Children Parent | Leaf Parent
data Children = Children Node Node
data Parent = Parent Node


k :: Integer
k = 1


main :: IO ()
main = putStrLn $ show $ length leaves  -- hangs


leaves :: [Node]
leaves = concat leafPairs
    where
        valuePairs = chunksOf 2 [1..2^k]                   -- I can trace this
        parentValues = map sum valuePairs                  -- and this
        parents = getParents $ zip parentValues leafPairs  -- but not this
        leafPairs = zipWith build parents valuePairs       -- or this
        build parent [valueA, valueB] = [Node valueA r, Node valueB r]
            where r = Leaf $ Parent parent


-- We're down to one parent, so make it a root
getParents :: [(Integer, [Node])] -> [Node]
getParents [(value, [childA, childB])] = [Node value $ Root children]
    where children = Children childA childB

# ¿ Jun 5, 2017 22:27

205b: Mar 25, 2007

timick posted:

The problem is the the recursive definition of leafPairs, which depends on parents which depends on leafPairs and so on.

Is it a problem specifically because I'm trying to pattern match in getParents? Otherwise, I thought mutually dependent declarations were ok.

# ¿ Aug 30, 2017 08:45

205b: Mar 25, 2007

timick posted:

It has to do with the way that you've defined your tree. To create the parent node you need two child nodes, to create a child node you need a root node. Evaluating the tree will loop forever. Keep in mind that the parent field in a node is not a pointer or a reference to the parent node, it is a new copy of the parent node (which in turn will have new copies of child nodes...).

I'm not sure what you're after but would it be enough to have a leaf that looks like this instead?
code:
Leaf Integer
Where Integer would be the Integer value from the parent node.

I did need a distinct value for each node, but it turned out I could get away with a singly-linked tree, so I went with that. Just trying to wrap my head around what I did wrong. I think I get it now! What you're saying is that let x = 0:y; y = 1:x in x doesn't give you two nodes pointing at each other, but a chain of infinitely many nodes.

As a followup, how come length (let x = 0:y; y = 1:x in x) pegs my processor but my original example just sat there doing nothing?

# ¿ Aug 31, 2017 08:15

205b: Mar 25, 2007

dirby posted:

...

Sure, got that part, I was just unclear on whether the recursive definition would result in a cyclical list or an infinite list. It sounds like it's the latter, which explains why my tree didn't work.

Thanks both for the help!

# ¿ Sep 1, 2017 08:51

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Functional Programming: This thread is like a burrito