Search Results

Search found 1171 results on 47 pages for 'recursive cte'.

Page 1/47 | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >

  • SQL SERVER – CTE can be Updated

    - by Pinal Dave
    Today I have received a fantastic email from Matthew Spieth. SQL Server expert from Ohio. He recently had a great conversation with his colleagues in the office and wanted to make sure that everybody who reads this blog knows about this little feature which is commonly confused. Here is his statement and we will start our story with Matthew’s own statement: “Users often confuse CTE with Temp Table but technically they both are different, CTE are like Views and they can be updated just like views.“ Very true statement from Matthew. I totally agree with what he is saying. Just like him, I have enough, time came across a situation when developers think CTE is like temp table. When you update temp table, it remains in the scope of the temp table and it does not propagate it to the table based on which temp table is built. However, this is not the case when it is about CTE, when you update CTE, it updates underlying table just like view does. Here is the working example of the same built by Matthew to illustrate this behavior. Check the value in the base table first. USE AdventureWorks2012; -- Check - The value in the base table is updated SELECT Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738'; Now let us build CTE with the same data. ;WITH CTEUpd(ProductID, Name, ProductNumber, Color) AS( SELECT ProductID, Name, ProductNumber, Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738') Now let us update CTE with following code. -- Update CTE UPDATE CTEUpd SET Color = 'Rainbow'; Now let us check the BASE table based on which the CTE was built. -- Check - The value in the base table is updated SELECT Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738'; That’s it! You can update CTE and it will update the base table. Here is the script which you should execute all together. USE AdventureWorks2012; -- Check - The value in the base table is updated SELECT Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738'; -- Build CTE ;WITH CTEUpd(ProductID, Name, ProductNumber, Color) AS( SELECT ProductID, Name, ProductNumber, Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738') -- Update CTE UPDATE CTEUpd SET Color = 'Rainbow'; -- Check - The value in the base table is updated SELECT Color FROM [Production].[Product] WHERE ProductNumber = 'CA-6738'; If you are aware of such scenario, do let me know and I will post this on my blog with due credit to you. Reference: Pinal Dave (http://blog.sqlauthority.com)Filed under: PostADay, SQL, SQL Authority, SQL Query, SQL Server, SQL Tips and Tricks, SQL View, T SQL Tagged: CTE

    Read the article

  • SQL SERVER – Quiz and Video – Introduction to Hierarchical Query using a Recursive CTE

    - by pinaldave
    This blog post is inspired from SQL Queries Joes 2 Pros: SQL Query Techniques For Microsoft SQL Server 2008 – SQL Exam Prep Series 70-433 – Volume 2.[Amazon] | [Flipkart] | [Kindle] | [IndiaPlaza] This is follow up blog post of my earlier blog post on the same subject - SQL SERVER – Introduction to Hierarchical Query using a Recursive CTE – A Primer. In the article we discussed various basics terminology of the CTE. The article further covers following important concepts of common table expression. What is a Common Table Expression (CTE) Building a Recursive CTE Identify the Anchor and Recursive Query Add the Anchor and Recursive query to a CTE Add an expression to track hierarchical level Add a self-referencing INNER JOIN statement Above six are the most important concepts related to CTE and SQL Server.  There are many more things one has to learn but without beginners fundamentals one can’t learn the advanced  concepts. Let us have small quiz and check how many of you get the fundamentals right. Quiz 1) You have an employee table with the following data. EmpID FirstName LastName MgrID 1 David Kennson 11 2 Eric Bender 11 3 Lisa Kendall 4 4 David Lonning 11 5 John Marshbank 4 6 James Newton 3 7 Sally Smith NULL You need to write a recursive CTE that shows the EmpID, FirstName, LastName, MgrID, and employee level. The CEO should be listed at Level 1. All people who work for the CEO will be listed at Level 2. All of the people who work for those people will be listed at Level 3. Which CTE code will achieve this result? WITH EmpList AS (SELECT Boss.EmpID, Boss.FName, Boss.LName, Boss.MgrID, 1 AS Lvl FROM Employee AS Boss WHERE Boss.MgrID IS NULL UNION ALL SELECT E.EmpID, E.FirstName, E.LastName, E.MgrID, EmpList.Lvl + 1 FROM Employee AS E INNER JOIN EmpList ON E.MgrID = EmpList.EmpID) SELECT * FROM EmpList WITH EmpListAS (SELECT EmpID, FirstName, LastName, MgrID, 1 as Lvl FROM Employee WHERE MgrID IS NULL UNION ALL SELECT EmpID, FirstName, LastName, MgrID, 2 as Lvl ) SELECT * FROM BossList WITH EmpList AS (SELECT EmpID, FirstName, LastName, MgrID, 1 as Lvl FROM Employee WHERE MgrID is NOT NULL UNION SELECT EmpID, FirstName, LastName, MgrID, BossList.Lvl + 1 FROM Employee INNER JOIN EmpList BossList ON Employee.MgrID = BossList.EmpID) SELECT * FROM EmpList 2) You have a table named Employee. The EmployeeID of each employee’s manager is in the ManagerID column. You need to write a recursive query that produces a list of employees and their manager. The query must also include the employee’s level in the hierarchy. You write the following code segment: WITH EmployeeList (EmployeeID, FullName, ManagerName, Level) AS ( –PICK ANSWER CODE HERE ) SELECT EmployeeID, FullName, ” AS [ManagerID], 1 AS [Level] FROM Employee WHERE ManagerID IS NULL UNION ALL SELECT emp.EmployeeID, emp.FullName mgr.FullName, 1 + 1 AS [Level] FROM Employee emp JOIN Employee mgr ON emp.ManagerID = mgr.EmployeeId SELECT EmployeeID, FullName, ” AS [ManagerID], 1 AS [Level] FROM Employee WHERE ManagerID IS NULL UNION ALL SELECT emp.EmployeeID, emp.FullName, mgr.FullName, mgr.Level + 1 FROM EmployeeList mgr JOIN Employee emp ON emp.ManagerID = mgr.EmployeeId Now make sure that you write down all the answers on the piece of paper. Watch following video and read earlier article over here. If you want to change the answer you still have chance. Solution 1) 1 2) 2 Now compare let us check the answers and compare your answers to following answers. I am very confident you will get them correct. Available at USA: Amazon India: Flipkart | IndiaPlaza Volume: 1, 2, 3, 4, 5 Please leave your feedback in the comment area for the quiz and video. Did you know all the answers of the quiz? Reference: Pinal Dave (http://blog.sqlauthority.com) Filed under: Joes 2 Pros, PostADay, SQL, SQL Authority, SQL Query, SQL Server, SQL Tips and Tricks, T SQL, Technology

    Read the article

  • Prevent recursive CTE visiting nodes multiple times

    - by bacar
    Consider the following simple DAG: 1->2->3->4 And a table, #bar, describing this (I'm using SQL Server 2005): parent_id child_id 1 2 2 3 3 4 //... other edges, not connected to the subgraph above Now imagine that I have some other arbitrary criteria that select the first and last edges, i.e. 1-2 and 3-4. I want to use these to find the rest of my graph. I can write a recursive CTE as follows (I'm using terminology from MSDN): with foo(parent_id,child_id) as ( // anchor member that happens to select first and last edges: select parent_id,child_id from #bar where parent_id in (1,3) union all // recursive member: select #bar.* from #bar join foo on #bar.parent_id = foo.child_id ) select parent_id,child_id from foo However, this results in edge 3-4 being selected twice: parent_id child_id 1 2 3 4 2 3 3 4 // 2nd appearance! How can I prevent the query from recursing into subgraphs that have already been described? I could achieve this if, in my "recursive member" part of the query, I could reference all data that has been retrieved by the recursive CTE so far (and supply a predicate indicating in the recursive member excluding nodes already visited). However, I think I can access data that was returned by the last iteration of the recursive member only. This will not scale well when there is a lot of such repetition. Is there a way of preventing this unnecessary additional recursion? Note that I could use "select distinct" in the last line of my statement to achieve the desired results, but this seems to be applied after all the (repeated) recursion is done, so I don't think this is an ideal solution. Edit - hainstech suggests stopping recursion by adding a predicate to exclude recursing down paths that were explicitly in the starting set, i.e. recurse only where foo.child_id not in (1,3). That works for the case above only because it simple - all the repeated sections begin within the anchor set of nodes. It doesn't solve the general case where they may not be. e.g., consider adding edges 1-4 and 4-5 to the above set. Edge 4-5 will be captured twice, even with the suggested predicate. :(

    Read the article

  • Recursive CTE with alternating tables

    - by SOfanatic
    I've created a SQL fiddle here. Basically, I have 3 tables BaseTable, Files, and a LinkingTable. The Files table has 3 columns: PK, BaseTableId, RecursiveId (ChildId). What I want to do is find all the children given a BaseTableId (i.e., ParentId). The tricky part is that the way the children are found works like this: Take ParentId 1 and use that to look up a FileId in the Files table, then use that FileId to look for a ChildId in the LinkingTable, if that record exists then use the RecursiveId in the LinkingTable to look for the next FileId in the Files table and so on. This is my CTE so far: with CTE as ( select lt.FileId, lt.RecursiveId, 0 as [level], bt.BaseTableId from BaseTable bt join Files f on bt.BaseTableId = f.BaseTableId join LinkingTable lt on f.FileId = lt.FileId where bt.BaseTableId = @Id UNION ALL select rlt.FileId, rlt.RecursiveId, [level] + 1 as [level], CTE.BaseTableId from CTE --??? and this is where I get lost ... ) A correct output for BaseTableId = 1, should be: FileId|RecursiveId|level|BaseTableId 1 1 0 1 3 2 1 1 4 3 2 1

    Read the article

  • CTE to build a list of departments and managers (hierarchical)

    - by Milky Joe
    I need to generate a list of users that are managers, or managers of managers, for company departments. I have two tables; one details the departments and one contains the manager hierarchy (simplified): CREATE TABLE [dbo].[Manager]( [ManagerId] [int], [ParentManagerId] [int]) CREATE TABLE [dbo].[Department]( [DepartmentId] [int], [ManagerId] [int]) Basically, I'm trying to build a CTE that will give me a list of DepartmentIds, together with all ManagerIds that are in the manager hierarchy for that department. So... Say Manager 1 is the Manager for Department 1, and Manager 2 is Manager 1's Manager, and Manager 3 is Manager 2's Manager, I'd like to see: DepartmentId, ManagerId 1, 1 1, 2 1, 3 Basically, managers are able to deal with all of their sub-manager's departments. Building the CTE to return the Manager hierarchy was fairly simple, but I'm struggling to inject the Departments in there: WITH DepartmentManagers AS ( SELECT ManagerId, ParentManagerId, 0 AS Depth From Manager UNION ALL SELECT Manager.ManagerId, Manager.ParentManagerId, DepartmentManagers.Depth + 1 AS Depth FROM Manager INNER JOIN DepartmentManagers ON DepartmentManagers.ManagerId = Manager.ParentManagerId ) Can anyone help?

    Read the article

  • Recursive CTE Problem

    - by Chris
    Hi, I am trying to use a recursive CTE in SQL Server to build up a predicate formula from a table containing the underlying tree structure. For example, my table looks like: -------------------------- Id Operator/Val ParentId -------------------------- 1. 'OR' NULL 2. 'AND' 1 3. 'AND' 1 4. '' 2 5. 'a' 4 6. 'alpha' 4 : : : -------------------------- which represents ((a alpha) AND (b beta)) OR ((c gamma) AND (a < delta)). ParentId is a reference to the Id in the same table of the parent node. I want to write a query which will build up this string from the table. Is it possible? Thanks

    Read the article

  • SQL Server CTE referred in self joins slow

    - by Kharlos Dominguez
    Hello, I have written a table-valued UDF that starts by a CTE to return a subset of the rows from a large table. There are several joins in the CTE. A couple of inner and one left join to other tables, which don't contain a lot of rows. The CTE has a where clause that returns the rows within a date range, in order to return only the rows needed. I'm then referencing this CTE in 4 self left joins, in order to build subtotals using different criterias. The query is quite complex but here is a simplified pseudo-version of it WITH DataCTE as ( SELECT [columns] FROM table INNER JOIN table2 ON [...] INNER JOIN table3 ON [...] LEFT JOIN table3 ON [...] ) SELECT [aggregates_columns of each subset] FROM DataCTE Main LEFT JOIN DataCTE BananasSubset ON [...] AND Product = 'Bananas' AND Quality = 100 LEFT JOIN DataCTE DamagedBananasSubset ON [...] AND Product = 'Bananas' AND Quality < 20 LEFT JOIN DataCTE MangosSubset ON [...] GROUP BY [ I have the feeling that SQL Server gets confused and calls the CTE for each self join, which seems confirmed by looking at the execution plan, although I confess not being an expert at reading those. I would have assumed SQL Server to be smart enough to only perform the data retrieval from the CTE only once, rather than do it several times. I have tried the same approach but rather than using a CTE to get the subset of the data, I used the same select query as in the CTE, but made it output to a temp table instead. The version referring the CTE version takes 40 seconds. The version referring the temp table takes between 1 and 2 seconds. Why isn't SQL Server smart enough to keep the CTE results in memory? I like CTEs, especially in this case as my UDF is a table-valued one, so it allowed me to keep everything in a single statement. To use a temp table, I would need to write a multi-statement table valued UDF, which I find a slightly less elegant solution. Did some of you had this kind of performance issues with CTE, and if so, how did you get them sorted? Thanks, Kharlos

    Read the article

  • Apply a recursive CTE on grouped table rows (SQL server 2005).

    - by Evan V.
    Hi all, I have a table (ROOMUSAGE) containing the times people check in and out of rooms grouped by PERSONKEY and ROOMKEY. It looks like this: PERSONKEY | ROOMKEY | CHECKIN | CHECKOUT | ROW ---------------------------------------------------------------- 1 | 8 | 13-4-2010 10:00 | 13-4-2010 11:00 | 1 1 | 8 | 13-4-2010 08:00 | 13-4-2010 09:00 | 2 1 | 1 | 13-4-2010 15:00 | 13-4-2010 16:00 | 1 1 | 1 | 13-4-2010 14:00 | 13-4-2010 15:00 | 2 1 | 1 | 13-4-2010 13:00 | 13-4-2010 14:00 | 3 13 | 2 | 13-4-2010 15:00 | 13-4-2010 16:00 | 1 13 | 2 | 13-4-2010 15:00 | 13-4-2010 16:00 | 2 I want to select just the consecutive rows for each PERSONKEY, ROOMKEY grouping. So the desired resulting table is: PERSONKEY | ROOMKEY | CHECKIN | CHECKOUT | ROW ---------------------------------------------------------------- 1 | 8 | 13-4-2010 10:00 | 13-4-2010 11:00 | 1 1 | 1 | 13-4-2010 15:00 | 13-4-2010 16:00 | 1 1 | 1 | 13-4-2010 14:00 | 13-4-2010 15:00 | 2 1 | 1 | 13-4-2010 13:00 | 13-4-2010 14:00 | 3 13 | 2 | 13-4-2010 15:00 | 13-4-2010 16:00 | 1 I want to avoid using cursors so I thought I would use a recursive CTE. Here is what I came up with: ;with CTE (PERSONKEY, ROOMKEY, CHECKIN, CHECKOUT, ROW) as (select RU.PERSONKEY, RU.ROOMKEY, RU.CHECKIN, RU.CHECKOUT, RU.ROW from ROOMUSAGE RU where RU.ROW = 1 union all select RU.PERSONKEY, RU.ROOMKEY, RU.CHECKIN, RU.CHECKOUT, RU.ROW from ROOMUSAGE RU inner join CTE on RU.ROWNUM = CTE.ROWNUM + 1 where CTE.CHECKIN = RU.CHECKOUT and CTE.PERSONKEY = RU.PERSONKEY and CTE.ROOMKEY = RU.ROOMKEY) This worked OK for very small datasets (under 100 records) but it's unusable on large datasets. I'm thinking that I should somehow apply the cte recursevely on each PERSONKEY, ROOMKEY grouping on my ROOMUSAGE table but I am not sure how to do that. Any help would be much appreciated, Cheers!

    Read the article

  • SQL Server CTE Basics

    The CTE was introduced into standard SQL in order to simplify various classes of SQL Queries for which a derived table just wasn't suitable. For some reason, it can be difficult to grasp the techniques of using it. Well, that's before Rob Sheldon explained it all so clearly for us.

    Read the article

  • Difference between an LL and Recursive Descent parser?

    - by Noldorin
    I've recently being trying to teach myself how parsers (for languages/context-free grammars) work, and most of it seems to be making sense, except for one thing. I'm focusing my attention in particular on LL(k) grammars, for which the two main algorithms seem to be the LL parser (using stack/parse table) and the Recursive Descent parser (simply using recursion). As far as I can see, the recursive descent algorithm works on all LL(k) grammars and possibly more, whereas an LL parser works on all LL(k) grammars. A recursive descent parser is clearly much simpler than an LL parser to implement, however (just as an LL one is simply than an LR one). So my question is, what are the advantages/problems one might encounter when using either of the algorithms? Why might one ever pick LL over recursive descent, given that it works on the same set of grammars and is trickier to implement? Hopefully this question makes some amount of sense. Sorry if it doesn't - I blame my the fact that this entire subject is almost entirely new to me.

    Read the article

  • PHP: Recursive array function

    - by Industrial
    Hi everybody, I want to create a function that returns the full path from a set node, back to the root value. I tried to make a recursive function, but ran out of luck totally. What would be an appropriate way to do this? I assume that a recursive function is the only way? Here's the array: Array ( [0] => Array ( [id] => 1 [name] => Root category [_parent] => ) [1] => Array ( [id] => 2 [name] => Category 2 [_parent] => 1 ) [2] => Array ( [id] => 3 [name] => Category 3 [_parent] => 1 ) [3] => Array ( [id] => 4 [name] => Category 4 [_parent] => 3 ) ) The result I want my function to output when getting full path of node id#4: Array ( [0] => Array ( [id] => 1 [name] => Root category [_parent] => ) [1] => Array ( [id] => 3 [name] => Category 3 [_parent] => 1 ) [2] => Array ( [id] => 4 [name] => Category 4 [_parent] => 3 ) ) The notoriously bad example of my recursive skills: function recursive ($id, $array) { $innerarray = array(); foreach ($array as $k => $v) { if ($v['id'] === $id) { if ($v['_parent'] !== '') { $innerarray[] = $v; recursive($v['id'], $array); } } } return $innerarray; } Thanks!

    Read the article

  • Recursive move utility on Unix?

    - by Thomas Vander Stichele
    Sometimes I have two trees that used to have the same content, but have grown out of sync (because I moved disks around or whatever). A good example is a tree where I mirror upstream packages from Fedora. I want to merge those two trees again by moving all of the files from tree1 into tree2. Usually I do this with: rsync -arv tree1/* tree2 Then delete tree1. However, this takes an awful lot of time and disk space, and it would be much easier to be able to do: mv -r tree1/* tree2 In other words, a recursive move. It would be faster because first of all it would not even copy, just move the inodes, and second I wouldn't need a delete at the end. Does this exist ? As a test case, consider the following sequence of commands: $ mkdir -p a/b $ touch a/b/c1 $ rsync -arv a/ a2 sending incremental file list created directory ./ b/ b/c1 b/c2 sent 173 bytes received 57 bytes 460.00 bytes/sec total size is 0 speedup is 0.00 $ touch a/b/c2 What command would now have the effect of moving a/b/c2 to a2/b/c2 and then deleting the a subtree (since everything in it is already in the destination tree) ?

    Read the article

  • SQL Server 2008 ContainsTable, CTE, and Paging

    - by David Murdoch
    I'd like to perform efficient paging using containstable. The following query selects the top 10 ranked results from my database using containstable when searching for a name (first or last) that begins with "Joh". DECLARE @Limit int; SET @Limit = 10; SELECT TOP @Limit c.ChildID, c.PersonID, c.DOB, c.Gender FROM [Person].[vFullName] AS v INNER JOIN CONTAINSTABLE( [Person].[vFullName], (FullName), IS ABOUT ( "Joh*" WEIGHT (.4), "Joh" WEIGHT (.6)) ) AS k3 ON v.PersonID = k3.[KEY] JOIN [Child].[Details] c ON c.PersonID = v.PersonID JOIN [Person].[Details] p ON p.PersonID = c.PersonID ORDER BY k3.RANK DESC, FullName ASC, p.Active DESC, c.ChildID ASC I'd like to combine it with the following CTE which returns the 10th-20th results ordered by ChildID (the primary key): DECLARE @Start int; DECLARE @Limit int; SET @Start = 10; SET @Limit = 10; WITH ChildEntities AS ( SELECT ROW_NUMBER() OVER (ORDER BY ChildID) AS Row, ChildID FROM Child.Details ) SELECT c.ChildID, c.PersonID, c.DOB, c.Gender FROM ChildEntities cte INNER JOIN Child.Details c ON cte.ChildID = c.ChildID WHERE cte.Row BETWEEN @Start+1 AND @Start+@Limit ORDER BY cte.Row ASC

    Read the article

  • php run function on all images from one dir in recursive mode (noob)

    - by Steve
    hey guyz i have a function $result = create_watermark( 'input_file_name' ,'output_file_name'); i have dir called /images n have 500 images in it and all images are link images_(some_unknown_numbers).png (all png) now i want run them thru function in loop and want out put like /markedimage/images_1.png images_2.png images_3.png i need help how can i run them in loop and how out put name can change want run script on Ubuntu so we can use shell too if any body want check function it is here http://paste2.org/p/789149 plz provide me code because i m newbie thanks in advance

    Read the article

  • a non recursive approach to the problem of generating combinations at fault

    - by mark
    Hi, I wanted a non recursive approach to the problem of generating combination of certain set of characters or numbers. So, given a subset k of numbers n, generate all the possible combination n!/k!(n-k)! The recursive method would give a combination, given the previous one combination. A non recursive method would generate a combination of a given value of loop index i. I approached the problem with this code: Tested with n = 4 and k = 3, and it works, but if I change k to a number 3 it does not work. Is it due to the fact that (n-k)! in case of n = 4 and k = 3 is 1. and if k 3 it will be more than 1? Thanks. int facto(int x); int len,fact,rem=0,pos=0; int str[7]; int avail[7]; str[0] = 1; str[1] = 2; str[2] = 3; str[3] = 4; str[4] = 5; str[5] = 6; str[6] = 7; int tot=facto(n) / facto(n-k) / facto(k); for (int i=0;i<tot;i++) { avail[0]=1; avail[1]=2; avail[2]=3; avail[3]=4; avail[4]=5; avail[5]=6; avail[6]=7; rem = facto(i+1)-1; cout<<rem+1<<". "; for(int j=len;j>0;j--) { int div = facto(j); pos = rem / div; rem = rem % div; cout<<avail[pos]<<" "; avail[pos]=avail[j]; } cout<<endl; } int facto(int x) { int fact=1; while(x0) fact*=x--; return fact; }

    Read the article

  • Java Generics Type Safety warning with recursive Hashmap

    - by GC
    Hi, I'm using a recursive tree of hashmaps, specifically Hashmap map where Object is a reference to another Hashmap and so on. This will be passed around a recursive algorithm: foo(String filename, Hashmap<String, Object> map) { //some stuff here for (Entry<String, Object> entry : map.entrySet()) { //type warning that must be suppressed foo(entry.getKey(), (HashMap<String, Object>)entry.getValue()); } } I know for sure Object is of type Hashmap<String, Object> but am irritated that I have to suppress the warning using @SuppressWarnings("unchecked"). I'll be satisfied with a solution that does either a assert(/*entry.getValue() is of type HashMap<String, Object>*/) or throws an exception when it isn't. I went down the Generics route for compile type safety and if I suppress the warning then it defeats the purpose. Thank you for your comments, ksb

    Read the article

  • Tail-recursive implementation of take-while

    - by Giorgio
    I am trying to write a tail-recursive implementation of the function take-while in Scheme (but this exercise can be done in another language as well). My first attempt was (define (take-while p xs) (if (or (null? xs) (not (p (car xs)))) '() (cons (car xs) (take-while p (cdr xs))))) which works correctly but is not tail-recursive. My next attempt was (define (take-while-tr p xs) (let loop ((acc '()) (ys xs)) (if (or (null? ys) (not (p (car ys)))) (reverse acc) (loop (cons (car ys) acc) (cdr ys))))) which is tail recursive but needs a call to reverse as a last step in order to return the result list in the proper order. I cannot come up with a solution that is tail-recursive, does not use reverse, only uses lists as data structure (using a functional data structure like a Haskell's sequence which allows to append elements is not an option), has complexity linear in the size of the prefix, or at least does not have quadratic complexity (thanks to delnan for pointing this out). Is there an alternative solution satisfying all the properties above? My intuition tells me that it is impossible to accumulate the prefix of a list in a tail-recursive fashion while maintaining the original order between the elements (i.e. without the need of using reverse to adjust the result) but I am not able to prove this. Note The solution using reverse satisfies conditions 1, 3, 4.

    Read the article

  • Right recursive grammar or left recursive?

    - by user2485710
    I have little to no knowledge of what I'm about to ask, so I would like a suggestion based on the level of skills required to implemented a parser for the given grammar ( since I'm a beginner in this kind of formal approach to parsers and languages ). Just by going back of a couple of years, this situation reminds me a little of Pascal grammar vs C/C++ grammar, this left vs right stuff. But I'm not going to do any of that, my purpose is to implement a simple parser for a markup language for documents like Markdown. So considering that I'm starting with a markup language in mind, I want to keep things simple, which is the easiest one to handle between this 2 options and why . Another kind of grammar could be an easier option for me ? If yes which one do you suggest ?

    Read the article

  • scheme recursive lambda

    - by Mike
    Is there a way to have a recursive lambda expression in scheme without relying an external identifier? I know you can have (define fact (lambda (n) (if (= n 0) 1 (fact (- n 1)))) but it would be nice if fact wasn't hard coded in the lambda expression, it seems improper.

    Read the article

1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >