list,function,recursion,lisp,common-lisp , Common Lisp - Writing a function that detects circular lists


Common Lisp - Writing a function that detects circular lists

Question:

Tag: list,function,recursion,lisp,common-lisp

I have an assignment for my CS functional languages class where we must write a function able to detect whether or not a given list is circular at its beginning. The function has to be recursive. Let's name it circular :

* (setf list1 '(a b c d))
* (rplacd (cddr list1) list1)
* list1
#1=(A B C . #1#)
* (circular list1)
t
* (circular '(a b c a b c))
nil

Now, I know how to check for circularity in this case : at some point along the recursion, an atom a cons in the list is going to share the same address as the list itself, hence the circularity. Here is my function so far :

(defun circular (list &aux list2)
  (setf list2 list)
  (cond
    ((null list) nil)
    ((eq (car list) list2) t)
    (t (circular (cdr list))) ) )

I thought that by comparing the car of list against list2 at every point of the recursion the function would eventually return a result, but while the function does work for non-circular lists, it becomes infinitely recursive when I try to use it on a circular list. I am sure that I am missing something incredibly obvious here, but still, any help would be immensely appreciated!


Answer:

This problem can be solved using the tortoise and hare algorithm where you have two cursors scanning though tortoise at one cons at a time and hare at double speed starting on the second element. If the tortoise and hare is the same element you have a cycle.

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (loop :for tortoise on list
        :for hare on (cdr list) :by #'cddr
        :thereis (eq tortoise hare)))

So imagine you have the list, #1=(a b c . #1#) or more precisely '#1=(a . #2=(b . #3=(c . #1#))). It contains 3 cons with address 1,2,3 and each cons have one of symbolic value a, b, c.

If I write the car of the tortoise and hare you'll see the hare wraps around and eventually ends up at the same cons as tortoise

Iteration 1 2 3
Tortoise  a b c
Hare      b a c
              ^ match

Only thing you need to do is reimplement it using recursion. It would look something like this:

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (labels ((aux (tortoise hare)
        (cond ((null hare) <??>)
              ((eq tortoise hare) <??>)
              (t (aux <??> <??>)))))
    (aux list (cdr list))))

EDIT

A naive and simpler version that only checks references back to the first cons can be done like this:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (loop :for cursor on (cdr list)
        :thereis (eq cursor list)))

Only thing you need to do is reimplement it using recursion. It would look something like this:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (labels ((aux (cursor)
        (cond ((null cursor) <??>)
              ((eq cursor list) <??>)
              (t (aux <??>)))))
    (aux (cdr list))))

If the cycle happens but not in the first cons this will not terminate.

(cyclic-1-p '(1 . #1=(2 3 . #1#))) ; never halts

Related:


C++ need help figuring out word count in function. (Ex. Hello World = 2)


c++,function
I'm figuring out the algorithm on this function and it keeps crashing at runtime, here's the code snippet: int wordCounter(char usStr[]) { int index= 0, punct= 0; while(usStr[index]!= '\0') //If it's not the end of the sentence if(usStr[index]== ' ') //If it finds a space index++; while(usStr[index]== '\0') //If it's...

Replace paragraph in HTML with new paragraph using Javascript


javascript,function,onload,getelementbyid,appendchild
I am attempting to replace a p in my HTML doc with a paragraph created in Javascript. Once the page loads, two will be replaced with t. var two = document.getElementById("two"); document.onload = function myFunction() { var p = document.createElement("p"); var t = document.createTextNode("I am the superior text"); p.appendChild(t); document.getElementById("p");...

how to insert into python nested list


python,list,list-comprehension
I want to insert an item into a list inside a list. I'm wondering if someone can show me. list5 = [[], [(1,2,3,4), 2, 5]] print("1. list5", list5) list5.insert(0, (2,5,6,8)) print("2. list5", list5) Output: 1. list5 [[], [(1, 2, 3, 4), 2, 5]] 2. list5 [(2, 5, 6, 8), [],...

Django: Handling several page parameters


python,django,list,parameters,httprequest
I have several possible parameter to process in a page. Assume x0, x1, x2,..., x1000. It seems awkward to get and process them one by one by request.GET.get('x0'), request.GET.get('x1'), ... Any idea to put them in a list, so that they can be processed in a loop....

How does ((a++,b)) work? [duplicate]


c,function,recursion,comma
This question already has an answer here: What does the comma operator `,` do in C? 8 answers In the below block of code, I am trying to understand how the line return reverse((i++, i)) is working. #include <stdio.h> void reverse(int i); int main() { reverse(1); } void reverse(int...

JSLint won't recognize getElementById


javascript,function,getelementbyid,jslint
JSLint gives errors with simple function, running on brackets with JSLint. Javascript: function soundSorry() { getElementById("player").play(); } Error codes: 2 Missing 'use strict' statement. getElementById("player").play(); 2 'getElementById' was used before it was defined. getElementById("player").play(); Any ideas?...

Stopping condition on a recursive function - Haskell


string,function,haskell,if-statement,recursion
So, I have this function which aims to align the text on the left without cutting words(only white spaces). However my problem is that I cannot find a stopping condition of the function and it goes infinitely. f n "" = "" --weak condition f n s = if n...

Filter list using Boolean array


python,list
How can I use boolean array as index to filter a list? For example: >>> l = ['a','b','c'] >>> b = [True,False,False] >>> l[b] The result should be: ['a'] I know numpy support it but want to know how to solve in Python. >>> import numpy as np >>> l...

Is it possible to use $(this) in a function called from another function?


jquery,function,this
Sorry for the question title, I know it's not very well worded, but I couldn't really explain what I'm asking in a summary. I have a JQuery function tied to the click event of an element. For reasons that may well be flawed (other than making more sense to me...

Can I put StreamReaders in a list? Or any other way to read a lot of text files at once?


c#,list,text,streamreader
I have a lot of text files and want to read them all by once, how do I do this? This is my code till now: List<StreamReader> lijst = new List<StreamReader>(); using (StreamReader qwe = new StreamReader("C:\\123.txt")) using (StreamReader qwer = new StreamReader("C:\\1234.txt")) lijst.Add(qwe); lijst.Add(qwer); But I get an ObjectDisposedException(Cannot...

Update input number variable onclick


javascript,jquery,html,function
I am trying to create a calculator style thing, where you put in how many years into a input, you hit submit and it gives you different results below without reloading the page. I have all the calculations working right now, but I just cant get the input number variable...

How to skip a function


function,python-2.7
I am learning python and trying to make a little game. So my question is can you define a function but skip it and use it later. EX. def func() print"1,2,3,4" func() def func2() print "counting" func() func2() How would I skip func but still be able to print it...

Sort when values are None or empty strings python


python,list,sorting,null
I have a list with dictionaries in which I sort them on different values. I'm doing it with these lines of code: def orderBy(self, col, dir, objlist): if dir == 'asc': sorted_objects = sorted(objlist, key=lambda k: k[col]) else: sorted_objects = sorted(objlist, key=lambda k: k[col], reverse=True) return sorted_objects Now the problem...

Java Get and then remove from a list


java,list,setter,getter,instances
In my code i have a list of instances of a class. And i want to get a attribute of 1 instance which is ArrayList. In this class i have implement getters and setters. So I call listofinstances.get(i).getArrayList().remove(0); in order to remove the 1st item of this list. Is this...

I need to make sure that only certain characters are in a list?


python,regex,string,list,python-2.7
I have this to get input and put it in a list: def start(): move_order=[raw_input("Enter your moves: ").split()] And I only want the characters A, D, S, C, H (it's for a game >_>) to be allowed. I've tried using the regular expressions stuff: if re.match('[ADSCH]+', [move_order]) is False: print...

How can I minimize this function in R?


r,function,optimization,mathematical-optimization
I'm attempting to write a formula that will determine a value of a that minimizes the function output myfun (i.e. a-fptotal). MWE: c <- as.matrix(c(.25,.5,.25)) d <- as.matrix(c(10000,12500,15000)) e <- 700 f <- 1.1 tr <- .30 myfun <- function(a) { b <- max(a-e,0) df <- data.frame(u1=c(c*b*.40),u2=c(c*b*.60)) df$year <- 1:nrow(df)...

Can't understand this Javascript function (function overloading)


javascript,function,methods,overloading
I'm reading Secrets of Javascript Ninja and came across an example that I cannot fully understand. This same example was cited by some other user here before, but their doubts are different than mine. Here is the example: function addMethod(object, name, fn) { var old = object[name]; object[name] = function(){...

Decremented value called in the recursion in Haskell


string,function,haskell,recursion,parameters
So, I have this function that aligns the text to the left for a given column width. I have already fixed some of its problems, but I am unable to make it not use the decremented parameter once it is called, but to return to the starting value of n....

Operand order in Scala List.prepend (::)


list,scala,operators
Odersky has brilliantly optimized Java syntax, enabling object calls without dots and parenthesis. I.e. instead of list.prepend(item), you now simply write list :: item, which also turns language operators into simple object methods. Here, List defines :: (prepend) operator. However, you normally write it vice-verse in Scala, using item ::...

MySQL function with parameters syntax error


mysql,regex,function
I'm trying to convert this query to a MySQL function SET @v1 := ( SELECT count(id) as count FROM article_category where (title like "About Usd") or (title like "About Usd-%" and title regexp '[0-9]$') ); INSERT INTO `article_category` (`title`,`meta_data`,`meta_description`) VALUES ( IF(@v1 <= 0, "About Usd", CONCAT("About Usd","-",@v1) ), "ddddD",...

Python - Using a created list as a parameter


python,list,loops,if-statement,compare
When I run my code it tells me: Type Error: unorderable types: str() < float(). I can't figure out why it won't let me compare these two numbers. The list I am using is defined, and the numbers in it have been redefined as floats, so I'm not sure what...

PercentOfSum(fld, condfld) SSRS Equivalent


function,reporting-services,crystal-reports,ssrs-2008,ssrs-2008-r2
Crystal Reports has a built-in function PercentOfSum(fld, condfld) (documentation here). How can I achieve the same functionality in SSRS?

why java API prevents us to call add and remove together?


java,list,collections,listiterator
As per Java API- IllegalStateException - if neither next nor previous have been called, or remove or add have been called after the last call to next or previous remove()- Removes from the list the last element that was returned by next() or previous() (optional operation). This call can only...

join two different list by id into one list


c#,list,join,merge,automapper
I've got two different list of two different objects. Then i got one list of a viewmodel that contains properties from both the objects and i want them to be joined into that list. //Product public string id { get; set; } public string unitMeasurement { get; set; } public...

ZipList with Scalaz


list,scala,scalaz,applicative
Suppose I have a list of numbers and list of functions to apply to numbers: val xs: List[Int] = List(1, 2, 3) val fs: List[Int => Int] = List(f1, f2, f3) Now I would like to use an Applicative to apply f1 to 1, f2 to 2, etc. val ys:...

Calling function and passing arguments multiple times


python,function,loops
I want to call the function multiple time and use it's returned argument everytime when it's called. For example: def myfunction(first, second, third): return (first+1,second+1,third+1) 1st call: myfunction(1,2,3) 2nd call is going to be pass returned variables: myfunction(2,3,4) and loop it until defined times. How can I do such loop?...

chunk of data into fixed lengths chunks and then add a space and again add them all as a string


regex,list,join,ironpython,findall
I have got hex values as a85b080040010000. I want it to be as a8 5b 08 00 40 01 00 00. I have done it by using below code. But I have to work with very large data. So I want computed time to be very low. import binascii import...

Implementing a dictionary function to calculate the average of a list


python,list,dictionary
As always, I've attempted this for awhile before I proceed to ask a question on here. I know there are several attempts at answering this, but none really worked for what I needed. Here are the instructions: Implement the following three functions (you should use an appropriate looping construct to...

Easiest way to Add lines wrong a .txt file to a list


c#,string,list,streamreader
At the moment I am opening the .txt file twice, once to get the number of all the lines, second to add a line to a list as much as how much lines there are in the .txt file. Is there an easier/better way to do this? This is my...

group indices of list in list of lists


python,list
I am looking for an elegant solution for the following problem. I have a list of ints and I want to create a list of lists where the indices with the same value are grouped together in the order of the occurrences of said list. [2, 0, 1, 1, 3,...

List of tuples from (a, all b) to (b, all a)


python,list,python-2.7,tuples
I am starting with a list of tuples (a,all b). I want to end with a list of tuples (b,all a). For example: FROM (a1,[b1,b2,b3]) (a2,[b2]) (a3,[b1,b2]) TO (b1,[a1,a3]) (b2[a1,a2,a3]) (b3,[a1] How do I do this using Python 2? Thank you for your help....

How can I iterate through nested HTML lists without returning the “youngest” children?


javascript,jquery,html,list,loops
Fiddle: https://jsfiddle.net/zayjeLrk/12/ I want to iterate through an HTML nested list that is 3-layers deep. <ul> <li>animals <ul> <li>birds <ul> <li>crow</li> <li>parrot</li> </ul> </li> <li>reptiles</li> </ul> </li> <li>plants</li> <li>bugs</li> </ul> I want it to iterate through the list so that it returns the elements in this order (note, this isn't...

Stopping list selection in Python 2.7


python,list,python-2.7
Imagine that I have an order list of tuples: s = [(0,-1), (1,0), (2,-1), (3,0), (4,0), (5,-1), (6,0), (7,-1)] Given a parameter X, I want to select all the tuples that have a first element equal or greater than X up to but not including the first tuple that has...

Python 2.7 “list index out of range”


python,list
I keep getting "IndexError: list index out of range", the code does fine with things like "s = 'miruxsexxzlbveznyaidekl'" but this particular length makes it throw an error. Can anyone help me understand what I did wrong here, not just give me the answer? (I'd like to not have to...

jQuery - Value in Function


jquery,arrays,function
My array: array.name = "Thiago"; array.date = "01/01/1990"; I want a function like this: function myFunc( array, fieldToCompare, valueToCompare ) { if( array.fieldToCompare == "Thiago" ) alert(true); } myFunc( myArray, name, "Thiago" ); is it possible?...

Create array/list of many objects(initially unknown amount) by tag


c#,arrays,list,unity3d,gameobject
I'm currently working on a radar system for my space game, and I am trying to work out how to add gameobjects, by tag, to either a list or array that can then be used in other methods. I can't do this manually because I will be procedurally generating each...

sum of Digits through Recursion


java,function,recursion,sum,digit
I am trying to make a recursive function which should return the sum of digits. The function should have only one argument. So far I have this; public int sumDigits(int n) { if(n%10 == n) // last digit remains return n; else{ int rightdigit; rightdigit = n%10; // taking out...

How do I read this list and parse it?


python,list
I'm using requests and the output I get from the sites API is a list, I've been stuck trying to parse it to get the data from it. I use r = requests.get(urlas, params=params) r.json() to get the data I want. Here is a snippet of the list [{'relation_type': None,...

SQL average age comparison function returns null


mysql,sql,function,datetime
So, I'm working in MySQL, writing a function that averages the ages of women and men from a table and compares them, and returns which is greater. Dates are in the format of YYYY-MM-DD, and I'm using DATEDIFF(). The function appears to work correctly, but when I run the script,...

session value in javascript cannot be set


javascript,function,session
I am quite new to javascript, I wonder why my session value in javascript wont be set to 1 even I tried. When call this function again, the value of the session will change again. My javascript code as below. <script type="text/javascript"> function Confirm() { alert(<%=Session["Once"]%> != 1); var value...

Get element starting with letter from List


java,android,list,indexof
I have a list and I want to get the position of the string which starts with specific letter. I am trying this code, but it isn't working. List<String> sp = Arrays.asList(splited); int i2 = sp.indexOf("^w.*$"); ...

Python regular expression, matching the last word


python,regex,list
I've the following problem. I'm looking to find all words in a string that typically looks like so HelloWorldToYou Notice, each word is capitalized as a start followed by the next word and so on. I'm looking to create a list of words from it. So the final expected output...

Call known function (with parameters) in class whose name is defined by string variable


java,function,class,variables
I have a bunch of classes of various names and each has a performLogic function that accepts a number of preset parameters (always the same): public final class DoSomeAction extends SetupAction { public void performLogic(param1, param2... I want a way where I can call it like this: String actionName =...

represent an index inside a list as x,y in python


python,list,numpy,multidimensional-array
I have a list which contains 1000 integers. The 1000 integers represent 20X50 elements of dimensional array which I read from a file into the list. I need to walk through the list with an indicator in order to find close elements to each other. I want that my indicator...

Reduction of list dimensions in Python


python,list,indexing,nodes
I'm trying to assign classes to a list of nodes, and separate all nodes into separate lists based on class tag. For example, if we have the following code: #define number of classes MaxC=5 index=[4 4 5 1 4 1 4 5 4 4 3 1 3 3 1 1]...

Counting bytes received by posix read()


c,function,serial-port,posix
I get confused with one line of code: temp_uart_count = read(VCOM, temp_uart_data, 4096); I found more about read function at http://linux.die.net/man/3/read, but if everything is okay it returns 0, so how we can get num of bytes received from that? temp_uart_count is used to count how much bytes we received...

Why cant I refer to a random index in my 4D list, while I know it exists?


c#,list,for-loop,dimensions
I got a 4D list, and I want where I want to display only the [k][3][j][z], but this isnt working. I checked all the counts and they are all 5+, so 3[4] should work... for (int k = 0; k < lijst4D.Count; k++) { for (int i = 0; i...

Update list of items in c#


c#,linq,list,updates
I would like to know if you can suggest me an efficient way to update a list of items in c#. Here is a generic example: If CurrentList is [ {Id: 154, Name: "George", Salary: 10 000} {Id: 233, Name: "Alice", Salary: 10 000}] And NewList is [ {Id: 154,...

Selecting and removing a html select option without selecting by index or ID, using vanilla JavaScript


javascript,function,select,options
I need to remove an option on a select box, and I've figured out a potential solution in the code below, but it doesn't feel particularly 'safe' (if another developer decided to add an option to the backend, the option will re-appear). Is there a better way of achieving this...

Stuck on Structs(c++)


c++,function,struct
Okay so this is what Ive been asked to do "make a struct called Coordinate that contains the latitude and longitude of a point on the surface of the Earth. The struct should also store a label or name for the coordinate (e.g., “Calgary”). Both the latitude and longitude member...