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:


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?...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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]...

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)...

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 =...

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...

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?...

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...

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....

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?

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...

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 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), [],...

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...

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...

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...

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,...

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...

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...

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?...

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....

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...

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(){...

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...

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,...

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",...

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...

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...

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...

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.*$"); ...

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 ::...

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 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...

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,...

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 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,...

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:...