get1 [] n = error "List is too small"
get1 xs n|n<0 = error "Use positive numbers"          
get1 (x:xs) 0 = x
get1 (x:xs) n = get1 xs (n-1)

I have get function made myself, but my check for positive numbers goes for O(n). What should i do to make this O(1)? I'm new in haskell, so recommend me something simple, please

CodePudding user response：

If you stay with linked lists, you cannot do better than O(n). So if you want better, you'll have to use a different data structure; for O(1) essentially your only choice is an array, though there are many options if you allow yourself to relax to O(log n). And remember, for all n, log n < 30.

CodePudding user response：

[Int] is a linked list type. Using this data structure, there's no faster way to access the Nth element than traveling through the first N ones.

In the case you are using get1 in another function f and you find that to be too slow, you either need to switch to a new data structure or (very commonly) rewrite f to avoid get1. For instance, this is a common beginner mistake:

-- add 10 to each element in the list
add10 :: [Int] -> [Int]
add10 xs = [ 10   get1 xs i | i <- [0 .. length xs-1] ]

This function "works" but is rather inefficient. For a list of length N, we pay O(N) for each get1, and we make O(N) such calls, for a total of O(N^2) where, intuitively, O(N) would suffice.

The solution, in this case, is to avoid working with indices i but directly scan the list.

-- add 10 to each element in the list
add10 :: [Int] -> [Int]
add10 xs = [ 10   x | x <- xs ]

In some other languages, to scan a list/array/sequence we need to work with indices. In Haskell, that's not the proper way to do it.

As a thumb rule, if you are a beginner and start working with lists, you should avoid functions like length, !! in most cases. I'd also recommend to avoid partial functions like head, tail. In general, many problems can be efficiently solved with lists using recursion and pattern matching, folds, maps, zip/zipWith, list comprehensions, and the like.