Skip to main content

mastodon - Link to source

I need some #lisp help.

I'm stuck on a recursion exercise - have been for 2 days!

We're given a at a structure a list of lists, where each such list is of the form (person mother father) .. and so a lot of these together create a family tree.

I want to write a function lineage x y which returns a list of ancestors from x to y ... eg x, mother of x, father of prev, y .... or NIL if y is not an ancestor of x.

I found this easy in #prolog (I wrote this prologbyexample.blogspot.com/2… ) but not #lisp.


7 - Introducing Recursion

Recursion is an important technique in many programming languages, especially declarative languages like prolog. It enables elegant and ...
prologbyexample.blogspot.com
#lisp #prolog
This entry was edited (3 weeks ago)
Unknown parent

screwlisp
mastodon - Link to source
screwlisp
• •
an answer

Sensitive content

@Alexander Burger
in reply to Tariq

Alexander Burger
mastodon - Link to source
Alexander Burger
• •

In #PicoLisp it could be pb1n.de/?c3be0c

#Lisp

#lisp #picolisp
in reply to Alexander Burger

screwlisp
mastodon - Link to source
screwlisp
• •
An answer in acl2

Sensitive content

This entry was edited (3 weeks ago)

screwlisp reshared this.

in reply to screwlisp

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
An answer in acl2

Sensitive content

@screwlisp @Alexander Burger
in reply to Jencel Panic

screwlisp
mastodon - Link to source
screwlisp
• •
An answer in acl2

Sensitive content

@Tariq @Alexander Burger
This entry was edited (3 weeks ago)
in reply to screwlisp

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
An answer in acl2

Sensitive content

@screwlisp @Alexander Burger
in reply to Jencel Panic

screwlisp
mastodon - Link to source
screwlisp
• •
An answer in acl2

Sensitive content

@Jencel Panic @Tariq @Alexander Burger
in reply to screwlisp

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
An answer in acl2

Sensitive content

@screwlisp @Alexander Burger
in reply to Jencel Panic

screwlisp
mastodon - Link to source
screwlisp
• •
An answer in acl2

Sensitive content

@Jencel Panic @Tariq @Alexander Burger
in reply to screwlisp

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
An answer in acl2

Sensitive content

@screwlisp @Alexander Burger
in reply to Jencel Panic

screwlisp
mastodon - Link to source
screwlisp
• •
An answer in acl2

Sensitive content

@Jencel Panic @Tariq @Alexander Burger
in reply to screwlisp

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
an answer

Sensitive content

@screwlisp @Alexander Burger

screwlisp reshared this.

Unknown parent

screwlisp
mastodon - Link to source
screwlisp
• •
an answer

Sensitive content

@Tariq @Alexander Burger
This entry was edited (3 weeks ago)

screwlisp reshared this.

in reply to Jencel Panic

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
an answer

Sensitive content

@screwlisp @Alexander Burger
in reply to screwlisp

screwlisp
mastodon - Link to source
screwlisp
• •
an answer

Sensitive content

@Jonathan Lamothe @Jencel Panic @Jeremy List @Tariq @Alexander Burger
in reply to Tariq

Tariq
mastodon - Link to source
Tariq
• •

here is a portion of of the data structure:

(defvar family
'((linda nil nil)
(suzanne colin deirdre)
(bruce arthur kate)
(charles arthur kate)
(david arthur kate)
(ellen arthur kate)
(george frank linda)
(hillary frank linda)
(andre nil nil) ...

This entry was edited (3 weeks ago)
in reply to Tariq

Riley S. Faelan
mastodon - Link to source
Riley S. Faelan
• •

Beware that if you're always doing list scans, your complexity can really blow up. Once you will have solved the problem in the classic Lisp style, you might also want to look into implementing it using a hash table. (These are part of the Common Lisp standard library.)

And then, if you have time left over and are curious abou Common Lisp's deep(er) internals, via the package system.

This entry was edited (3 weeks ago)
in reply to Tariq

Riley S. Faelan
mastodon - Link to source
Riley S. Faelan
• •

This is a common Prolog problem because Prolog's way of pattern-matching can make the hard part implicit. Lisp doesn't do it on its own (although there's some tricks that could be pulled by CLOS, and, as always, one could start by implementing Prolog in Lisp, and then resort to the teapot principle).

What you're trying to do is searching for a pah through a (directed acyclic) graph, or depth-first search (aassuming you don't want o convert the input daaset into something different as a part of th procssing). Graph algorithms can be a useful searchword, or possibly ToCword. Most introductory programming (or Lisp programming) textbooks discuss at least the basic ideas of graph traversal, partly because, well, making graph problems relatively easy is kind of what Lisp is good at, and for a long while, didn't really have major competitors in.

This entry was edited (3 weeks ago)
in reply to Riley S. Faelan

Tariq
mastodon - Link to source
Tariq
• •

@riley

so if I try to think lisp rather than prolog by brain tells me I need to recursively follow all the paths from that starting point and use "nil" to fail the wrong ones.

that suggests some use of "OR path1 path2 path3 ... " where only the correct path with non-NIL is returned.

but I can't seem to get to the next step

@Riley S. Faelan
in reply to Tariq

Riley S. Faelan
mastodon - Link to source
Riley S. Faelan
• •

That's kind of the essence of depth-first search, yes.

I'm not quite sure if that's what you have in mind, but perhaps it helps: you won't be able to follow all the paths in a single OR. You'll have to follow them one by one (or via an abstract function that does that for you). You might want to use the LOOP mechanism for this. (Common Lisp has a particularly fancy looping tool.)

in reply to Riley S. Faelan

Tariq
mastodon - Link to source
Tariq
• •

@riley

Thanks I'll keep trying.

We haven't done loop yet so I'll think of other ways.

@Riley S. Faelan
in reply to Tariq

IPmonger
mastodon - Link to source
IPmonger
• •
@riley Try this "common sense" approach. If I asked you to solve this problem by hand, how would you do it?
@Riley S. Faelan
in reply to IPmonger

Tariq
mastodon - Link to source
Tariq
• •

@IPmonger @riley

That's how I would do it by hand.. to follow paths to find the one that starts with x and leads to y, and fail the ones that ended not af y.

Perhaps that's why I'm struggling? My common sense approach is too complex?

@Riley S. Faelan @IPmonger
in reply to Tariq

IPmonger
mastodon - Link to source
IPmonger
• •

@riley Try to approach it more simply. Imagine each data entry is on a 3"x5" index card and they are collectively stored in a small box of an appropriate size.

Now, I ask you to personally use the cards to determine the lineage from linda to albert. What do you do specifically?

@Riley S. Faelan
in reply to IPmonger

Tariq
mastodon - Link to source
Tariq
• •

@IPmonger @riley

In real life I would put start and end on the table and work in both directions forward from x and backwards from y.

By including the y I can reduce the search space

But that seems too complex for code.

@Riley S. Faelan @IPmonger
in reply to Tariq

Riley S. Faelan
mastodon - Link to source
Riley S. Faelan
• •

Computerised search on datasets like this is generally done in only direction, unless you'rea dealing with a large dataset and need heuristics, in which case there's some really interesting "like electricity" algorithms and heuristic pruning or search order techniques, generally falling under breadth-first search strategies, that may, indeed, search in both directions at once. These are probably out of the scope of this exercise, though. (The hint is, working on these would teach you graph algorithms, and you're supposed to work on learning how to think in Lisp.)

But sometimes, it can be useful for the one direction to go in the other way than what seems obvious.

The reasons for going only one way are numerous, some good, some so-so. For one, computers do not have human-like intuition, which factors into the optimal manual search patterns. For another, it's customary to aim for as simple algorithms as one can get away with. And historically, computer memory used to be very limited, so it paid to have both code and datasets to be tiny. Recall that Lisp is one of the two oldest programming languages still in actual use. Even COBOL is newer. When Lisp first came out, the concept of a computer being built of transistors, rather than thermionic valves, was the bleeding edge of tech, and the legendary PDP-1 got by with less than three thousand transistors, and only 4KiWords of memory in standard configuration. Modern computers are many orders of magnitude more capable, but some habits of these times are still culturally hard to break.

@IPmonger

@IPmonger
This entry was edited (3 weeks ago)
in reply to screwlisp

Jonathan Lamothe
friendica (DFRN) - Link to source
Jonathan Lamothe
•
an answer

@screwlisp Here's my naïve solution that I haven't bothered running through a compiler:

data People a = People
  { person :: a
  , mother :: Maybe (People a)
  , father :: Maybe (People a)
  }

lineage :: Eq a => a -> a -> People a -> [a]
lineage start end people = case findPerson start people of
  Nothing -> []
  Just subtree -> findTo end subtree

findPerson :: Eq a => a -> People a -> Maybe (People a)
findPerson p people = if person people == p
  then Just people
  else (mother people >>= findperson p) <> (father people >>= findPerson p)

findTo :: Eq a => a -> People a -> [a]
findTo p people = if person people == p
  then [p]
  else case (findTo p <$> mother people) <> (findTo p <$> father people) of
    Nothing -> []
    Just r -> person people : r

This assumes that all the person values are unique. It will potentially fail if not.

Edit: renaming Person to People and bugfix

Edit 2: Actually, I don't think this will discard failed subtrees correctly.

Edit 3: Were I to try to fix this, I'd first change the type signature of findTo to Eq a => a -> People a -> Maybe [a] but I'm doing this all from a phone, not a real computer, so I'll leave that as an exercise to the reader.

@screwlisp
in reply to Jonathan Lamothe

Jencel Panic
mastodon - Link to source
Jencel Panic
• •
an answer

Sensitive content

@Jonathan Lamothe @screwlisp

This website uses cookies. If you continue browsing this website, you agree to the usage of cookies.

⇧