Avatar of agbell

agbell's solution

to Simple Linked List in the Haskell Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Write a simple linked list implementation that uses Elements and a List.

The linked list is a fundamental data structure in computer science, often used in the implementation of other data structures. They're pervasive in functional programming languages, such as Clojure, Erlang, or Haskell, but far less common in imperative languages such as Ruby or Python.

The simplest kind of linked list is a singly linked list. Each element in the list contains data and a "next" field pointing to the next element in the list of elements.

This variant of linked lists is often used to represent sequences or push-down stacks (also called a LIFO stack; Last In, First Out).

As a first take, lets create a singly linked list to contain the range (1..10), and provide functions to reverse a linked list and convert to and from arrays.

When implementing this in a language with built-in linked lists, implement your own abstract data type.

Hints

To complete this exercise, you need to create the data type LinkedList, and implement the following functions:

  • datum
  • fromList
  • isNil
  • new
  • next
  • nil
  • reverseLinkedList
  • toList

You will find a dummy data declaration and type signatures already in place, but it is up to you to define the functions and create a meaningful data type, newtype or type synonym.

Getting Started

For installation and learning resources, refer to the exercism help page.

Running the tests

To run the test suite, execute the following command:

stack test

If you get an error message like this...

No .cabal file found in directory

You are probably running an old stack version and need to upgrade it.

Otherwise, if you get an error message like this...

No compiler found, expected minor version match with...
Try running "stack setup" to install the correct GHC...

Just do as it says and it will download and install the correct compiler version:

stack setup

Running GHCi

If you want to play with your solution in GHCi, just run the command:

stack ghci

Feedback, Issues, Pull Requests

The exercism/haskell repository on GitHub is the home for all of the Haskell exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue. We'll do our best to help you!

Source

Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. http://www.brpreiss.com/books/opus8/html/page96.html#SECTION004300000000000000000

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Tests.hs

{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

import Test.Hspec                (Spec, it, shouldBe)
import Test.Hspec.Runner         (configFastFail, defaultConfig, hspecWith)
import Test.QuickCheck           (property)
import Test.QuickCheck.Arbitrary (Arbitrary, arbitrary)

import LinkedList
  ( datum
  , fromList
  , isNil
  , next
  , new
  , nil
  , reverseLinkedList
  , toList
  , LinkedList
  )

instance (Arbitrary a) => Arbitrary (LinkedList a) where
  arbitrary = fromList <$> arbitrary

nthDatum :: LinkedList a -> Int -> a
nthDatum xs 0 = datum xs
nthDatum xs n = nthDatum (next xs) (pred n)

main :: IO ()
main = hspecWith defaultConfig {configFastFail = True} specs

specs :: Spec
specs = do

            let n1   = new (1 :: Int) nil
            let n21  = new 2 n1
            let n321 = new 3 n21
            let fl1  = fromList [1 :: Int]
            let fl21 = fromList [2, 1 :: Int]
            let r1   = reverseLinkedList n1
            let r12  = reverseLinkedList n21
            let r123 = reverseLinkedList n321
            let msg  = "Should work for any type, not just Int!"

            it "constructor" $ do
                isNil nil               `shouldBe` True
                isNil n1                `shouldBe` False
                datum n1                `shouldBe` 1
                isNil (next n1)         `shouldBe` True
                isNil n21               `shouldBe` False
                datum n21               `shouldBe` 2
                isNil (next n21)        `shouldBe` False
                datum (next n21)        `shouldBe` 1
                isNil (next $ next n21) `shouldBe` True

            it "toList" $ do
                toList nil `shouldBe` ([] :: [Int])
                toList n1  `shouldBe` [1]
                toList n21 `shouldBe` [2, 1]

            it "fromList" $ do
                isNil (fromList [])      `shouldBe` True
                datum fl1                `shouldBe` 1
                isNil (next fl1)         `shouldBe` True
                datum fl21               `shouldBe` 2
                datum (next fl21)        `shouldBe` 1
                isNil (next $ next fl21) `shouldBe` True

            it "reverseLinkedList" $ do
                isNil (reverseLinkedList nil) `shouldBe` True
                datum r1                      `shouldBe` 1
                isNil (next r1)               `shouldBe` True
                datum r12                     `shouldBe` 1
                datum (next r12)              `shouldBe` 2
                isNil (next $ next r12)       `shouldBe` True
                datum r123                    `shouldBe` 1
                datum (next r123)             `shouldBe` 2
                datum (next $ next r123)      `shouldBe` 3

            it "roundtrip" $ do
                (toList . fromList) []      `shouldBe` ([]      :: [Int])
                (toList . fromList) [1]     `shouldBe` ([1]     :: [Int])
                (toList . fromList) [1, 2]  `shouldBe` ([1, 2]  :: [Int])
                (toList . fromList) [1..10] `shouldBe` ([1..10] :: [Int])

            it "has an unconstrained type variable" $ do
                (toList . fromList) msg     `shouldBe` msg
                (toList . fromList) [1..10] `shouldBe` ([1..10] :: [Integer])

            it "arbitrary reverseLinkedList" $
                property $ \(xs :: LinkedList Int) ->
                  reverseLinkedList xs == (fromList . reverse . toList) xs

            it "arbitrary (fromList . toList)" $
                property $ \(xs :: LinkedList Int) ->
                  (fromList . toList) xs == xs

            it "arbitrary (toList . fromList)" $
                property $ \(xs :: [Int]) ->
                  (toList . fromList) xs == xs

            it "arbitrary (reverseLinkedList . reverseLinkedList)" $
                property $ \(xs :: LinkedList Int) ->
                  (reverseLinkedList . reverseLinkedList) xs == xs

            it "arbitrary datum" $
                property $ \(xs :: [Int]) ->
                  let ll = fromList xs
                      sameNthDatum n = nthDatum ll n == xs !! n
                      indices = [0..pred $ length xs] in
                    all sameNthDatum indices
{-# LANGUAGE DeriveFoldable #-}
module LinkedList (datum, next, nil, isNil, fromList, toList, reverseLinkedList, new) where

import qualified Data.Foldable as Fold
import Data.Foldable (toList)

data LinkedList a =
  Nil
  | LinkedList { datum ::  a, next :: LinkedList a }
    deriving (Show, Fold.Foldable)

nil :: LinkedList a
nil = Nil

isNil :: LinkedList a -> Bool
isNil Nil = True
isNil _ = False

new :: a -> LinkedList a -> LinkedList a
new = LinkedList

fromList :: [a] -> LinkedList a
fromList = Fold.foldr LinkedList Nil

reverseLinkedList :: LinkedList a -> LinkedList a
reverseLinkedList = Fold.foldl' (flip LinkedList) Nil

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?