Solution to get n-th from last element in a linked list

readme.md

Overview

The problem is a generalization of the one explained in How to find the 3rd element from end in linked list in Java and basically consists of finding the element at position last - n in a Linked List which of course does not provide

• Random Access Semantic

• Length Semantic

but just the next() semantic

Probably the most interesting thing of this solution (as the problem is not too difficult) is it has been implemented in Haskell emulating the Linked List with a Standard List and without cheating hence making use just of the next() semantic

solution.hs

-- Solution to the following problem: How to find the i-th element from last in a Linked List 
-- Generalization of a problem described here 
-- How to find the 3rd element from end in linked list in Java
-- https://javarevisited.blogspot.com/2016/07/how-to-find-3rd-element-from-end-in-linked-list-java.html?fbclid=IwAR3DZU_RbE9irGKvIHQ-PUkCl5E04YS_AtY5kw9ybHeQf0ezYDSr4mnVQzY#ixzz5jI60o38w

-- Description 
-- 1. Emulated a Linked List with a Standard List, of course without "cheating" so no Random Element Access and no Access to List Length if not to represent the list end (which is typically represented by a NULL Ptr) 
-- 2. The only available list navigation method is next() whose return value needs to be represented as a Maybe Monad (at the end of the list there is no valid next element)
-- 3. The solution algo is always "tortoise and hare" (actually in this case they have same speed and a gap of n elements)
-- 4. the initialize() lambda is used to verify the list has enough elements to navigate 
-- 5. the actual O(N) list navigation is performed with the navigate_to_last() internal lambda which just using next() semantic moves the 2 pointers together until the list end is observed and at the point the second index identifies the desired element 

import Data.Maybe 

next :: [a] -> Int -> Maybe a 
next [] _ = Nothing 
next arr i 
  | i < last_valid = Just (arr!!(i+1))
  | i == last_valid = Nothing 
  | otherwise = Nothing 
  where 
  last_valid = ((length arr)-1) 


find_last_n :: [Int] -> Int -> Maybe Int 
find_last_n arr n 
  | (initialize arr n 0) == Nothing = Nothing
  | otherwise = Just (arr!!(navigate_to_last arr n 0))
  where 
  navigate_to_last arr i j 
    | (next arr i) == Nothing = j 
    | otherwise = navigate_to_last arr (i+1) (j+1)
  initialize arr n i 
    | ((next arr i) == Nothing) && (i<n) = Nothing 
    | otherwise = Just 0 



val :: Maybe Int -> String 
val Nothing = "Nothing"
val (Just x) = (show x) 


main = do 
  let a = [21, 25, 32, 56, 47, 96, 102]
  print (next a 2)


  --print (val (find_last_n a 2))
  print (find_last_n a 2)